Last active
April 20, 2018 17:22
-
-
Save josh-hernandez-exe/adb8a4cb8de7838c6b532991b019ecb7 to your computer and use it in GitHub Desktop.
Combinatoric Enumeration in C# Based of `itertools` model from python
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System.Linq; | |
using System.Collections.Generic; | |
namespace Combinatoric.Enumeration | |
{ | |
public static class CombinatoricEnumeration | |
{ | |
// https://docs.python.org/2/library/itertools.html#itertools.combinations | |
public static IEnumerable<List<T>> Combinations<T>(this IEnumerable<T> items, int r) | |
{ | |
int n = items.Count(); | |
if (r > n) yield break; | |
T[] pool = items.ToArray(); | |
int[] indices = Enumerable.Range(0, r).ToArray(); | |
yield return indices.Select(x => pool[x]).ToList(); | |
while (true) | |
{ | |
int i = indices.Length-1; | |
while(i>=0 && indices[i] == i + n - r) | |
i-=1; | |
if(i<0) yield break; | |
indices[i] += 1; | |
for(int j=i+1; j<r; j+=1) | |
indices[j] = indices[j-1] + 1; | |
yield return indices.Select(x => pool[x]).ToList(); | |
} | |
} | |
public static IEnumerable<List<T>> Permutations<T>(this IEnumerable<T> items) => items.Permutations(items.Count()); | |
// https://docs.python.org/2/library/itertools.html#itertools.permutations | |
public static IEnumerable<List<T>> Permutations<T>(this IEnumerable<T> items, int r) | |
{ | |
int n = items.Count(); | |
if (r > n) yield break; | |
T[] pool = items.ToArray(); | |
int[] indices = Enumerable.Range(0, n).ToArray(); | |
int[] cycles = Enumerable.Range(n-r+1,r).Reverse().ToArray(); | |
yield return indices.Take(r).Select(x => pool[x]).ToList(); | |
while(true) | |
{ | |
int i = cycles.Length-1; | |
while(i>=0) | |
{ | |
cycles[i] -= 1; | |
if(cycles[i] ==0) | |
{ | |
// rotate indices from i to end | |
int tempInt = indices[i]; | |
int[] tmpArray = indices.Skip(i).ToArray(); | |
tmpArray.CopyTo(indices,i); | |
indices[indices.Length-1] = tempInt; | |
cycles[i] = n - i; | |
} | |
else | |
{ | |
int j = indices.Length - cycles[i]; | |
(indices[i], indices[j]) = (indices[j], indices[i]); | |
yield return indices.Take(r).Select(x => pool[x]).ToList(); | |
break; | |
} | |
i-=1; | |
} | |
if(i<0) yield break; | |
} | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System.Linq; | |
using System.Collections.Generic; | |
using Microsoft.VisualStudio.TestTools.UnitTesting; | |
using Combinatoric.Enumeration; | |
namespace Combinatoric.Enumeration.Test | |
{ | |
[TestClass] | |
public class CombinatoricEnumerationTest | |
{ | |
[DataTestMethod] | |
[DataRow(5,1,5)] | |
[DataRow(5,2,10)] | |
[DataRow(5,5,1)] | |
[DataRow(7,1,7)] | |
[DataRow(7,3,35)] | |
[DataRow(7,7,1)] | |
[DataRow(9,1,9)] | |
[DataRow(9,4,126)] | |
[DataRow(9,9,1)] | |
[DataRow(11,1,11)] | |
[DataRow(11,5,462)] | |
[DataRow(11,11,1)] | |
[DataRow(15,1,15)] | |
[DataRow(15,7,6435)] | |
[DataRow(15,15,1)] | |
public void CombinationTest(int n, int r, int nCr) | |
{ | |
int[] items = Enumerable.Range(0, n).ToArray(); | |
var allCombinations = new HashSet<HashSet<int>>(); | |
foreach(List<int> combination in items.Combinations(r)) | |
{ | |
foreach(int item in combination) | |
Assert.IsTrue(items.Contains(item),$"Not an item in original pool of items: {item}"); | |
string combStr = string.Join(",", combination); | |
var combSet = new HashSet<int>(combination); | |
Assert.IsTrue(combination.Count() == r,$"Number of items in the combination is different that the expected: |{combStr}| != {r}"); | |
Assert.IsFalse(allCombinations.Contains(combSet),$"Duplicate combination created: {combStr}"); | |
allCombinations.Add(combSet); | |
} | |
int numElements = allCombinations.Count(); | |
Assert.IsTrue(numElements == nCr,$"Nmber of combination generated is not the same as the expected amount: {numElements} (actual) != {nCr} (expected)"); | |
} | |
[DataTestMethod] | |
[DataRow(5,1,5)] | |
[DataRow(5,2,20)] | |
[DataRow(5,5,120)] | |
[DataRow(7,1,7)] | |
[DataRow(7,3,210)] | |
[DataRow(7,7,5040)] | |
[DataRow(9,1,9)] | |
[DataRow(9,4,3024)] | |
[DataRow(9,9,362880)] | |
[DataRow(11,1,11)] | |
[DataRow(11,5,55440)] | |
[DataRow(15,1,15)] | |
[DataRow(15,5,360360)] | |
public void PermutationTest(int n, int r, int nPr) | |
{ | |
int[] items = Enumerable.Range(0, n).ToArray(); | |
var allPermutations = new HashSet<List<int>>(); | |
foreach(List<int> permutation in items.Permutations(r)) | |
{ | |
foreach(int item in permutation) | |
Assert.IsTrue(items.Contains(item),$"Not an item in original pool of items: {item}"); | |
string permStr = string.Join(",", permutation); | |
Assert.IsTrue(permutation.Count() == r,$"Number of items in the permutation is different that the expected: |{permStr}| != {r}"); | |
Assert.IsFalse(allPermutations.Contains(permutation),$"Duplicate permutation created: {permStr}"); | |
allPermutations.Add(permutation); | |
} | |
int numElements = allPermutations.Count(); | |
Assert.IsTrue(numElements==nPr,$"Nmber of permutation generated is not the same as the expected amount: {numElements} (actual) != {nPr} (expected)"); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment