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

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

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

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

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.

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