Problem Statement: Given a set of elements 1 to n and a set S of n sets whose union equals everything, the problem is to find the minimum numbers of subsets equal the set in a pair of 2.
Concept: This problem is to solve the set problems. We can use permutations and combinations to solve this problem.
Illustration:
Input: All Possible Combination = {{1,2}, {3,4}, {8,9}, {10,7}, {5,8}, {11,6}, {4,5}, {6,7}, {10,11},}
Numbers = {1,2,3,4,5,6,7,8,9,10,11}
Output: The short combination was : [[1, 2], [3, 4], [8, 9], [10, 7], [5, 8], [11, 6]]
Input: All Possible Combination = {{1,2}, {3,4}, {2,7}, {5,3}, {4,5}, {6,7}, }
Numbers = {1,2,3,4,5,6,7}
Output: The short combination was : [[1, 2], [3, 4], [5, 3], [6, 7]]
Approach:
- At first, we give the possible sets and numbers of combinations as input in an array.
- Create a list and store all of them.
- Taking a Set and store the solution in that set.
- Call the shortest combo function
- This function takes a set as input and throws an exception if size greater than 20
- Iterates the size of all possible combinations and the new Set
- It then right shifts the value and then ending it to 1, we add all the solutions to the array List.
- This array List is returned by eliminating the duplicate values in the List
Implementation:
Example
Java
// Java Program to Solve Set Cover Problem// assuming at Maximum 2 Elements in a Subset// Importing input output classesimport java.io.*;// Importing necessarily required utility classes// from java.util packageimport java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.Comparator;import java.util.LinkedHashSet;import java.util.List;import java.util.Set;// Main classpublic class GFG { // Interface // Declaring the interface thereby taking // abstract methods of the interface interface Filter<T> { boolean matches(T t); } // Method 1 // Declaring a method-'shortcombo' // Declaring in form of set also returning a set private static <T> Set<T> shortcombo(Filter<Set<T> > filter, List<T> sets) { // Taking the size of the set final int size = sets.size(); // Condition check // If the size of the set is greater than 25 // We throw an exception like too many combinations if (size > 20) throw new IllegalArgumentException( "Too many Combinations"); // Now the comb will left shift 1 time of size int comb = 1 << size; // Taking a set with reference possible // this Arraylist will contain all the possible // solution List<Set<T> > possible = new ArrayList<Set<T> >(); // Taking a loop which iterates till comb for (int i = 0; i < comb; i++) { // Taking a lInkedHashSet of reference // combination Set<T> combination = new LinkedHashSet<T>(); // Taking a loop and iterating till size for (int j = 0; j < size; j++) { // If now we right shift i and j // and then ending it with 1 // This possible logic will give us how many // combinations are possible if (((i >> j) & 1) != 0) // Now the combinations are added to the // set combination.add(sets.get(j)); } // It is added to the possible reference possible.add(combination); } // Collections can be now sorted accordingly // using the sort() method over Collections class Collections.sort( possible, new Comparator<Set<T> >() { // We can find the minimum length by taking // the difference between sizes of possible // list public int compare(Set<T> a1, Set<T> a2) { return a1.size() - a2.size(); } }); // Now we take the iteration till possible for (Set<T> possibleSol : possible) { // Then we check for matching of the possible // solution // If it does we return the solution // If it doesnot we return null if (filter.matches(possibleSol)) return possibleSol; } return null; } // Method 2 // Main method public static void main(String[] args) { // Taking all the possible combinations // Custom entries in array Integer[][] all = { { 1, 2 }, { 3, 4 }, { 8, 9 }, { 10, 7 }, { 5, 8 }, { 11, 6 }, { 4, 5 }, { 6, 7 }, { 10, 11 }, }; // Here is the list of numbers to be chosen from // Again, custom entries in array Integer[] solution = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }; // Here let us take set as an object of an ArrayList List<Set<Integer> > sets = new ArrayList<Set<Integer> >(); // Now taking an array of the function all for (Integer[] array : all) // Now taking those elements and adding them to // an LinkedHashSet sets.add(new LinkedHashSet<Integer>( Arrays.asList(array))); // Now taking a set integer sol and // setting it as solution final Set<Integer> sol = new LinkedHashSet<Integer>( Arrays.asList(solution)); // Now taking a filter to check the values Filter<Set<Set<Integer> > > filter = new Filter<Set<Set<Integer> > >() { // Now taking boolean function matches // This function helps iterate all values // over the integers variable which adds // up all that to an union which will give // us the desired result public boolean matches( Set<Set<Integer> > integers) { Set<Integer> union = new LinkedHashSet<Integer>(); // Iterating using for-each loop for (Set<Integer> ints : integers) union.addAll(ints); return union.equals(sol); } }; // Now the below set will call the short combo // function This function will sort the shortest // combo Set<Set<Integer> > firstSol = shortcombo(filter, sets); // Print and display out the same System.out.println("The short combination was : " + firstSol); }} |
Output
The short combination was : [[1, 2], [3, 4], [8, 9], [10, 7], [5, 8], [11, 6]]
