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]]
