Combinatorics in .NET – Part I – Permutations, Combinations & Variations
[important] This is part 1 of a 2 part post on Combinatorics in .NetThe 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!
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.
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.
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
Pingback:Combinatorics in .NET – Part II – Creating a Nuget Package » try { } catch { } me | try { } catch { } me
Super helpful thanks!
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..
You’re either missing a reference or a using namespace.
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.
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.
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);
Entered a question on this board previously – what happened to it?
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.
how to pass multiple string array to get combination