Generate all combinations for a list of strings

Question

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; } }

I know this isn't quite what you were looking for but Microsoft has this system in beta that will auto generate inputs combinations for you. It is called Pex: research.microsoft.com/en-us/projects/pex — Christopher Rathermel
– Christopher Rathermel, Commented May 9, 2012 at 11:51
possible duplicate of Listing all permutations of a string/integer — Oliver
– Oliver, Commented May 9, 2012 at 12:13
You don't need recursion: stackoverflow.com/questions/10331229/… — Henrik
– Henrik, Commented May 9, 2012 at 12:29

Vlad · Accepted Answer · 2012-05-09 12:25:29Z

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(); }

Tim Schmelter · Accepted Answer · 2012-05-09 13:25:01Z

If you want all variations, have a look at this project to see how it's implemented.

http://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-C-G

But you can use it since it's open source under CPOL.

For example:

var allValues = new List<string>() { "A1", "A2", "A3", "B1", "B2", "C1" }; List<String> result = new List<String>(); var indices = Enumerable.Range(1, allValues.Count); foreach (int lowerIndex in indices) { var partVariations = new Facet.Combinatorics.Variations<String>(allValues, lowerIndex); result.AddRange(partVariations.Select(p => String.Join(" ", p))); } var length = result.Count; // 1956

Nans · Accepted Answer · 2016-10-15 07:02:10Z

One more recursive solution. From AllCombinations in below code, you will get all possible combinations. Logic:

Starting with one element.
Generate all possible combinations with it.
Move to next element and begin with step 2 again.

Code:

public class Combination<T> { private IEnumerable<T> list { get; set; } private int length; private List<IEnumerable<T>> _allCombination; public Combination(IEnumerable<T> _list) { list = _list; length = _list.Count(); _allCombination = new List<IEnumerable<T>>(); } public IEnumerable<IEnumerable<T>> AllCombinations { get { GenerateCombination(default(int), Enumerable.Empty<T>()); return _allCombination; } } private void GenerateCombination(int position, IEnumerable<T> previousCombination) { for (int i = position; i < length; i++) { var currentCombination = new List<T>(); currentCombination.AddRange(previousCombination); currentCombination.Add(list.ElementAt(i)); _allCombination.Add(currentCombination); GenerateCombination(i + 1, currentCombination); } } }

Collectives™ on Stack Overflow

Generate all combinations for a list of strings

3 Answers 3

Comments

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Linked

Related