Peter PitLock Peter PitLock - 1 month ago 5
C# Question

Partial Combinations/Permutations in C# - e.g. A,B,C = {A,B}, {A,C}, {B,C}

There are many brilliant implementations for Permutations - I chose Sam's answer in the link.

I also understand there is a difference between permutations and combinations but I don't know how to word this properly.

I need guidance on getting all unique partial combinations please, e.g.

A,B,C = {A,B}, {A,C}, {B,C}
A,B,C,D = {A,B,C},{A,B,D},{B,C,D},{A,C,D},{A,B}, {A,C}, {B,C}


From here I will pass this to the permutation function to get me all available
permutations,
e.g.
{A,B}, {B,A}, {A,C}, {C,A}
etc.

How can I get these (partial) subsets of the greater set?

Answer

It is quite easy to do recursively. You go through a virtual tree in the GetSubCombinations function, always returning the set without the current element first and then with the current element. On the last level (the first part of the GetSubCombinations function) you generate the lists that are being returned, either including the last element or being empty.

Code follows:

using System.Collections.Generic;


class Program {
    private static IEnumerable<List<char>> GetSubCombinations(char[] elements, uint startingPos)
    {
        // Leaf condition
        if (startingPos == elements.Length - 1)
        {
            yield return new List<char> {elements[startingPos]};
            yield return new List<char>();
            yield break;
        }

        // node splitting
        foreach (var list in GetSubCombinations(elements, startingPos + 1))
        {
            yield return list;
            list.Add(elements[startingPos]);
            yield return list;
            list.Remove(elements[startingPos]);
        }
    }

    private static IEnumerable<List<char>> GetPartialCombinations(char[] elements)
    {
        foreach (var c in GetSubCombinations(elements, 0))
        {
            // Here you can filter out trivial combinations,
            // e.g. all elements, individual elements and the empty set
            if (c.Count > 1 && c.Count < elements.Length)
                yield return c;
        }
    }


    static void Main(string[] args) {
        char[] elements = new char[] {'A', 'B', 'C'};
        foreach (var combination in GetPartialCombinations(elements))
        {
            foreach (char elem in combination)
                System.Console.Write(elem + ", ");
            System.Console.Write("\n");
        }
        return;
    }

}
Comments