How many combinations ?

Combinatorics in .NET – Part I – Permutations, Combinations & Variations

How many combinations?
How many combinations?
[important] This is part 1 of a 2 part post on Combinatorics in .Net

The solution is publicly available on github; https://github.com/eoincampbell/combinatorics

The library can be added to any .NET Soution via Nuget; https://nuget.org/packages/Combinatorics
[/important]

 

Recently while working on a project, I had need to generate combintations and permutations of sets of Inputs. In my search for a decent combinatorics library for .NET, (something which is missing from the BCL), I came across a Codeproject Article from Adrian Akision. The implementation included a C# Generics Collection implementation for creating Combinations, Permutations & Variations from an Input Set. Adrian very graciously allowed that I bundle up the code as a Class Library Solution on Github & then release the library via Nuget.

Permutations

Permutations provide all possible ordering of an input set of items. For n elements, P(n) = n!

Permutations
Permutations

 

e.g. How many ways can you shuffle the cards in a deck of playing cards.

 

 3 Digit Permutations
var integers = new List<int> {1, 2, 3};

var p = new Permutations<int>(integers);

foreach (var v in p)
{
    System.Diagnostics.Debug.WriteLine(string.Join(",", v));
}
Outputs:

1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1

Permutations with Repetition

Permutations with repetition take into account that some elements in the input set may repeat. In a 3 element input set, the number of permutations is 3! = 6. However if some of those input elements are repeated, then repeated output permutations would exist as well. Permutations with Repetition take account of repeating elements in the input set and do not disgard the repeated output sets. e.g.

Permutations with Repetition
Permutations with Repetition

 

 3 Digit Permutations without repetition
var integers = new List<int> {1, 1, 2};

var p = new Permutations<int>(integers, GenerateOption.WithoutRepetition);

foreach (var v in p)
{
    System.Diagnostics.Debug.WriteLine(string.Join(",", v));
}
Outputs:
1,1,2
1,2,1
2,1,1
 3 Digit Permutations with repetition
var integers = new List<int> {1, 1, 2};

var p = new Permutations<int>(integers, GenerateOption.WithRepetition);

foreach (var v in p)
{
    System.Diagnostics.Debug.WriteLine(string.Join(",", v));
}
Outputs:
1,1,2
1,2,1
1,1,2
1,2,1
2,1,1
2,1,1

Combinations

Combinations are subsets of items taken from a larger set of items. E.g. How many five card hands can be drawn from a  deck of 52 cards. In a set of items the total number of k sub-item combinations is calculated by n! / ( k! * (n – k)! ). In a deck of 52 cards, there are 2598960 combinations.

52 Cards Choose 5
52 Cards Choose 5

 

 3 Digit Combinations from a 5 digit input set.
var integers = new List {1, 2, 3, 4, 5};

var c = new Combinations(integers, 3);

foreach (var v in c)
{
    System.Diagnostics.Debug.WriteLine(string.Join(",", v));
}

Assert.AreEqual(10, c.Count);
Outputs:
1,2,3
1,2,4
1,2,5
1,3,4
1,3,5
1,4,5
2,3,4
2,3,5
2,4,5
3,4,5

Combinations with Repetition

Combinations with repetition allow for repeating input values in the output subsets. This would be similar to the combinations you can generate from repeatedly rolling a dice.

 

 2 Digit Combinations allowing Repetition from a set of 6
var integers = new List { 1, 2, 3, 4, 5, 6};
var c = new Combinations(integers, 2, GenerateOption.WithRepetition);
foreach (var v in c)
{         
    System.Diagnostics.Debug.WriteLine(string.Join(",", v));
}
Assert.AreEqual(21, c.Count);
Outputs:
1,1  1,2  1,3
1,4  1,5  1,6
2,2  2,3  2,4
2,5  2,6  3,3
3,4  3,5  3,6
4,4  4,5  4,6
5,5  5,6  6,6

Variations

Variations combine some of the properties of permutations & combinations. They are the set of all ordered subsets of a particular input set. If the order the elements are selected is unimportant in a combination, then it is important in a variation.

 

2 Digit Variations from a 3 Digit Input Set
var integers = new List {1, 2, 3};

var v = new Variations(integers, 2);

foreach (var vv in v)
{
    System.Diagnostics.Debug.WriteLine(string.Join(",", vv));
}
Outputs:
1,2
1,3
2,1
3,1
2,3
3,2

Variations with Repetition

2 Digit Variations from a 3 Digit Input Set with repetition allowed
var integers = new List { 1, 2, 3};

var v = new Variations(integers, 2, GenerateOption.WithRepetition);

foreach (var vv in v)
{
    System.Diagnostics.Debug.WriteLine(string.Join(",", vv));
}
Outputs:
1,1
1,2
1,3
2,1
2,2
2,3
3,1
3,2
3,3

In the next post we’ll look at the organisation of the solution and how it was deployed to Nuget.org

~Eoin Campbell

10 comments on “Combinatorics in .NET – Part I – Permutations, Combinations & Variations

  1. Pingback:Combinatorics in .NET – Part II – Creating a Nuget Package » try { } catch { } me | try { } catch { } me

  2. Mohit

    greetings
    i am getting an error on “Combinations” saying type or namespace not found, and “GenerateOption” saying does not exist int he current context.
    Assert also gives me an error saying it does not exist in the current context.

    please help me..
    thank you..

  3. Chris

    Can I suggest some more extensions to this wonderful library that will performs the same operations except doing so an a list of lists instead of over a single list? This way I can pass in an arbitrary number of lists, each with an arbitrary length, and get all the different combinations of those lists.

  4. Alfonso

    Greetings,
    I really like you work but it seems not to work in VS 2013. Specifically the method Combinations returns only the items of the first parameter, and not the combinations form that list of items.
    Any help would be great.
    Thanks.

  5. SCollege

    Thanks very much for the code.

    Sadly, the “Variations” and “Variations with Repetition” examples do not work for me.

    I get the error “Using the generic type ‘Combinatorics.Collections.Variations’ requires 1 type arguments”.

    I’ve tried several variations below but continue to receive the same error:

    var integers = new List { 1, 2, 3 };

    var integers = new List { 1, 2, 3 };

    int[] intList = { 1, 2, 3 };
    var integers = new List(intList);

    int[] intList = { 1, 2, 3 };
    List integers = new List(intList);

    List integers = new List();
    integers.Add(1);
    integers.Add(2);

  6. Alfonse

    is there any way this library can be efficiently used to only enumerate “stars and bars” solutions?

    Specifically, only showing variations with repetitions where the sum of the digits is a constant:

    X1 + X2 + X3 + X4 + X5 = 50

    it’s trivial enough to loop through and test, but the number of possibilities rapidly gets out of hand.

Leave a Reply

Your email address will not be published. Required fields are marked *