All possible combinations from given sets but without repetition of sets’ internal elements

Question

I have some fixed sets of integers, with distict increasing values in each a set, for example:

{1, 2, 4}, {1, 3}, {2, 4}, {2, 7}, {3, 6}, {5, 6}, {3, 5, 7}.

Is there any algorithm or better C# code, generating all possible combinations from given sets but without repetition of their internal integers, i.e.

[{1, 2, 4}, {3, 6}] < all integers are unique

[{1, 2, 4}, {3, 5, 7}] < all integers are unique

[{1, 3}, {2, 4}, {5, 6}] <– all integers are unique.

and so on.

====================================

Here is possible organization of input data:

        var set1 = new HashSet<int>() { 1, 2, 4 };
        var set2 = new HashSet<int>() { 1, 3 };
        var set3 = new HashSet<int>() { 2, 4 };
        var set4 = new HashSet<int>() { 2, 7 };
        var set5 = new HashSet<int>() { 3, 6 };
        var set6 = new HashSet<int>() { 5, 6 };
        var set7 = new HashSet<int>() { 3, 5, 7 };

        var inputList = new List<HashSet<int>>();
        inputList.Add(set1);
        inputList.Add(set2);
        inputList.Add(set3);
        inputList.Add(set4);
        inputList.Add(set5);
        inputList.Add(set6);
        inputList.Add(set7);

I need to obtain a list (or collection) of all possible lists (i.e. combinations) of sets from inputList with unique integers in each internal list (combination).

---

This question was marked as duplicate and as a question which already has an answer here: “Generating all Possible Combinations (8 answers)”. However, to my mind, it is essentially a DIFFERENT question:

• input data are not two arrays of the same length but rather a list of sets with different number of elements in each a set;

• equal elements may be present in different sets.

Answer 1

Personally I would approach this as a two part problem:

• Find the unique numbers in the list of numbers you have been provided. To do this in C# you could use a hashset, or you can use linq (which I assume you want because you tagged this with linq)
• Form all possible combinations of those numbers. This is already answered here: Getting all possible combinations from a list of numbers

Edit / Correction

So, delving further into the problem the goal here is to find combinations of the SETS not the individual numbers within those sets (as I had originally indicated above). With that in mind, I would do the following:

• Create a square, two dimensional array of booleans. Each boolean represents whether or not the set at that index conflicts with the set at the other index. Fill this in first.
• Use standard combinatorics (in the same was as mentioned above) but combine with checks to the list of booleans to discard invalid results.

I believe this should actually work. I (may) create an example here in a moment!

The Code

IMPORTANT: This isn't pretty or optimized in any sense of the word, but it does work and it does illustrate a way to solve this problem. One simple optimization would be to pass the Boolean array into the recursive step where the combinations are generated and stop the recursion as soon as a conflict is generated. That would save a ton of time and computing power. That said, I'll leave that as an exercise to the reader.

Just paste the following into a new console application and it should work. Best of luck!

    static void Main(string[] args)
    {
        // create/read sets here
        var integers = new List<int[]>(){new []{1,2,4}, new []{1,3}, new []{2, 4}, new []{2, 7}, new []{3, 6}, new []{5, 6}, new []{2, 5, 7}};

        // allocate/populate booleans - loop may be able to be refined
        var conflicts = new bool[integers.Count, integers.Count];
        for (var idx = 0; idx < integers.Count; idx++)
            for (var cmpIdx = 0; cmpIdx < integers.Count; cmpIdx++)
                conflicts[idx, cmpIdx] = integers[idx].Any(x => integers[cmpIdx].Contains(x));

        // find combinations (index combinations)
        var combinations = GetCombinations(integers.Count);

        // remove invalid entries
        for (var idx = 0; idx < combinations.Count; idx++)
            if (HasConflict(combinations[idx], conflicts))
                combinations.RemoveAt(idx--);

        // print out the final result
        foreach (var combination in combinations) PrintCombination(combination, integers);

        // pause
        Console.ReadKey();
    }


    // get all combinatins
    static List<Combination> GetCombinations(int TotalLists)
    {
        var result = new List<Combination>();

        for (var combinationCount = 1; combinationCount <= TotalLists; combinationCount++)
            result.AddRange(GetCombinations(TotalLists, combinationCount));

        return result;
    }

    static List<Combination> GetCombinations(int TotalLists, int combinationCount)
    {
        return GetCombinations(TotalLists, combinationCount, 0, new List<int>());
    }

    // recursive combinatorics - loads of alternatives including linq cartesian coordinates
    static List<Combination> GetCombinations(int TotalLists, int combinationCount, int minimumStart, List<int> currentList)
    {
        // stops endless recursion - forms final result
        var result = new List<Combination>();

        if (combinationCount <= 0)
        {
            if ((currentList ?? new List<int>()).Count > 0)
            {
                result.Add(new Combination() { sets = currentList });
                return result;
            }

            return null;
        }

        for (var idx = minimumStart; idx <= TotalLists - combinationCount; idx++)
        {
            var nextList = new List<int>();
            nextList.AddRange(currentList);
            nextList.Add(idx);

            var combinations = GetCombinations(TotalLists, combinationCount - 1, idx + 1, nextList);
            if (combinations != null) result.AddRange(combinations);
        }

        return result;
    }

    // print the combination
    static void PrintCombination(Combination value, List<int[]> sets)
    {
        StringBuilder serializedSets = new StringBuilder();

        foreach (var idx in value.sets)
        {
            if (serializedSets.Length > 0) serializedSets.Append(", ");
            else serializedSets.Append("{");

            serializedSets.Append("{");
            for (var setIdx = 0; setIdx < sets[idx].Length; setIdx++)
            {
                if (setIdx > 0) serializedSets.Append(", ");
                serializedSets.Append(sets[idx][setIdx].ToString());
            }
            serializedSets.Append("}");
        }

        serializedSets.Append("}");
        Console.WriteLine(serializedSets.ToString());
    }

    static bool HasConflict(Combination value, bool[,] conflicts)
    {
        for (var idx = 0; idx < value.sets.Count; idx++)
            for (var cmpIdx = idx + 1; cmpIdx < value.sets.Count; cmpIdx++)
                if (conflicts[value.sets[idx], value.sets[cmpIdx]]) return true;

        return false;
    }

    // internal class to manage combinations
    class Combination { public List<int> sets; }