Generate all combinations for a list of strings
c#, combinations, math
Solution
You can make in manually, using the fact that n-bit binary number naturally corresponds to a subset of n-element set.
private IEnumerable<int> constructSetFromBits(int i)
{
for (int n = 0; i != 0; i /= 2, n++)
{
if ((i & 1) != 0)
yield return n;
}
}
List<string> allValues = new List<string>()
{ "A1", "A2", "A3", "B1", "B2", "C1" };
private IEnumerable<List<string>> produceEnumeration()
{
for (int i = 0; i < (1 << allValues.Count); i++)
{
yield return
constructSetFromBits(i).Select(n => allValues[n]).ToList();
}
}
public List<List<string>> produceList()
{
return produceEnumeration().ToList();
}
Problem
I want to generate a list of all possible combinations of a list of strings (it's actually a list of objects, but for simplicity we'll use strings). I need this list so that I can test every possible combination in a unit test. So for example if I have a list of: ``` var allValues = new List<string>() { "A1", "A2", "A3", "B1", "B2", "C1" } ``` I need a `List<List<string>>` with all combinations like: ``` A1 A2 A3 B1 B2 C1 A1 A2 A1 A2 A3 A1 A2 A3 B1 A1 A2 A3 B1 B2 A1 A2 A3 B1 B2 C1 A1 A3 A1 A3 B1 etc... ``` A recursive function is probably the way to do it to get all combinations, but it seems harder than I imagined. Any pointers? Thank you. EDIT: two solutions, with or without recursion: ``` public class CombinationGenerator<T> { public IEnumerable<List<T>> ProduceWithRecursion(List<T> allValues) { for (var i = 0; i < (1 << allValues.Count); i++) { yield return ConstructSetFromBits(i).Select(n => allValues[n]).ToList(); } } private IEnumerable<int> ConstructSetFromBits(int i) { var n = 0; for (; i != 0; i /= 2) { if ((i & 1) != 0) yield return n; n++; } } public List<List<T>> ProduceWithoutRecursion(List<T> allValues) { var collection = new List<List<T>>(); for (int counter = 0; counter < (1 << allValues.Count); ++counter) { List<T> combination = new List<T>(); for (int i = 0; i < allValues.Count; ++i) { if ((counter & (1 << i)) == 0) combination.Add(allValues[i]); } // do something with combination collection.Add(combination); } return collection; } } ```