0

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?

Community
  • 1
  • 1
Peter PitLock
  • 1,823
  • 7
  • 34
  • 71
  • What sort of signature do you want on the method? Is it always returning sets that have one item missing or might you want to pass in a four item set and get all 2 item subsets? Or might you want to get all 2 and all three subsets? Its a little unclear from your examples exactly what exactly you are wanting... – Chris Oct 25 '16 at 10:31
  • Apologies for not being clear, I updated the question now to address that. For e.g. 4 items it would be all 2 items subsets and 3 items subsets. Thus all combinations > 1 and < GetUpperBound – Peter PitLock Oct 25 '16 at 10:36
  • Why are {A,B,C}, {A}, {B} and {C} not included in the first case? Those are also subsets of {A,B,C} – Jan Kukacka Oct 25 '16 at 10:37
  • Apologies @JanKukacka, I updated the question now, I was interested in only subsets but not full sets and not single sets. It is all combinations in between that I am battling with – Peter PitLock Oct 25 '16 at 10:41
  • Possible duplicate of [Listing all permutations of a string/integer](http://stackoverflow.com/questions/756055/listing-all-permutations-of-a-string-integer) – Manfred Radlwimmer Oct 25 '16 at 10:42
  • @ManfredRadlwimmer The question is asking for all partial combinations, *not* for all permutations. Very different. – RBarryYoung Oct 25 '16 at 10:55
  • 1
    @RBarryYoung I realized that a bit too late, but I retracted my close vote. – Manfred Radlwimmer Oct 25 '16 at 11:14

2 Answers2

2

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;
    }

}
Jan Kukacka
  • 1,196
  • 1
  • 14
  • 29
0

The difference between permutation to a combination is that in a permutation the order matters.

From what I understand you want all the Combinations, Thus all combinations that don't fill the exact set (You want to make a subset)

EX:

So for S = {A,B,C,D}, an example of a partial combination would be {A,C,B} as it doesn't care about the order and it doesn't contain the full set (ie. it is a subset of S)

The formula for Combination is N choose K

So your set has 4 elements (N) and you want a set of 3 or less (K)

So N!/K!(N-K)! 
3: = 4!/3!(4-3)! = (1x2x3x4)/(1x2x3)(1) = 4
2: = 4!/2!(2)! = 1x2x3x4/(1x2x1x2) = 6
1: = 4!/1!(4-1)! = 1x2x3x4/1x2x3 = 4

Thus answer is 14

If you want some code on how to implement a combination calculation: SOURCE

private static void GetCombination(List<int> list)
{
    double count = Math.Pow(2, list.Count);
    for (int i = 1; i <= count - 1; i++)
    {
        string str = Convert.ToString(i, 2).PadLeft(list.Count, '0');
        for (int j = 0; j < str.Length; j++)
        {
            if (str[j] == '1')
            {
                Console.Write(list[j]);
            }
        }
        Console.WriteLine();
    }
}
Community
  • 1
  • 1
Tristan van Dam
  • 172
  • 7
  • Sorry, I forgot to add the answer part. (It is in there now) – Tristan van Dam Oct 25 '16 at 10:50
  • In what way does this generate all partial combination subsets? It appears to merely count how many there are, not actually generate the subsets. – RBarryYoung Oct 25 '16 at 10:53
  • @TristanvanDam that is what is required please. I excluded the full amount of elements and single elements, but yes that is exactly it. – Peter PitLock Oct 25 '16 at 10:55
  • This is for generating the subset where you want three letters of the four. Ie: {A,B,C}, {B,C,D}, {C,D,A}, {D,A,B}. Note how they are in order as it is a combination. YOU would do the same for each relevant subset (S2) and (S1) – Tristan van Dam Oct 25 '16 at 10:56
  • @PeterPitLock I have rewritten it to make it more clear – Tristan van Dam Oct 25 '16 at 10:59