Possible combinations

Question

I'm having a array of Lists

List<string>[] possibleLines;

Array can be of different size also each each List<> can have different number of strings. Fore example

List<string>[0] - can have strings "first string", "second string"
List<string>[1] - "third string", "fourth string", "fifth string"

I need to get all possible combinations, each string must be from different list (array size may differ). For example

"first string", "fourth string"
"first string", "fifth string"
"second string", "fourth string"

and so on.

And to clarify, you want combinations and not permutations? — Mike Perrenoud
– Mike Perrenoud, Commented Jan 15, 2014 at 17:43
Can the strings in the results be in a different order than the lists they came from (is ["fourth string", "first string"]) a valid result?) , and if so, are different orderings considered different results (should we include both ["first string", "fourth string"] and ["fourth string", "first string"])? — nmclean
– nmclean, Commented Jan 15, 2014 at 17:47
@JonofAllTrades That's only an option with a number of lists known at compile time. Here it's not. — Servy
– Servy, Commented Jan 15, 2014 at 17:49
@JonofAllTrades Your solution isn't just nesting loops though; that's likely not even the "interesting" aspect of it. There's likely a recursive call, or something else along those lines, that allows it to be dynamic, and that is likely to be the "interesting" part of the solution. Generating combinations by just nesting loops is the solution when the number of collections is known. — Servy
– Servy, Commented Jan 15, 2014 at 18:27

Servy · Accepted Answer · 2014-01-15 17:43:38Z

What you're doing here is computing the Cartesian Product of an unknown number of collections. Eric Lippert describes how to write a solution to this problem in this blog post (which I strongly suggest you read to see how he comes up with this solution).

The code he ends up with as his result is:

static IEnumerable<IEnumerable<T>> CartesianProduct<T>( this IEnumerable<IEnumerable<T>> sequences) { IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() }; return sequences.Aggregate( emptyProduct, (accumulator, sequence) => from accseq in accumulator from item in sequence select accseq.Concat(new[] {item})); }

Love the article. I read through it and needed to visualize what was going on. Added an answer that adds the visualizing code to this solution. +1 for the great article!
Thank you it seems what I want. But I don't how to use it, I mean retrieve those combinations. Could you show an example.
@user2412672 You call CartesianProduct on possibleLines, and it gives you a sequence of sequences, where each inner sequence represents one combination. You can foreach the total result to do something for each combination, and then foreach each combination to print them out, for example.

joe_coolish · Accepted Answer · 2014-01-15 18:41:20Z

I thought this was a pretty cool math problem, but I wanted to visualize the actual process so I wrote this for anyone that wants to test out what Servy (well, Eric Lippert) wrote:

int length = 4; var lists = new List<List<string>>(); var random = new Random(1234); for(int i = 0; i < length; i++) { var inLength = random.Next(4, 8); var tempList = new List<string(); for (int j = 0; j < inLength; j++_ { tempList.Add(string.Format("{{String Coords: {0}, {1}}}", i, j)); } lists.Add(tempList); } var cp= lists.CartesianProduct(); var output = RenderString(cp);

and RenderString:

private static string RenderString(IEnumerable<IEnumerable<string>> cp) { var sb = new StringBuilder(); foreach (var item in cp) { sb.AppendLine(item.Aggregate((a, b) => a + b)); } return sb.ToString(); }

This will give you an output that looks like

{String Coords: 0, 0}{String Coords: 1, 0}{String Coords: 2, 0}{String Coords: 3, 0} {String Coords: 0, 0}{String Coords: 1, 0}{String Coords: 2, 0}{String Coords: 3, 1} {String Coords: 0, 0}{String Coords: 1, 0}{String Coords: 2, 0}{String Coords: 3, 2} {String Coords: 0, 0}{String Coords: 1, 0}{String Coords: 2, 0}{String Coords: 3, 3} {String Coords: 0, 0}{String Coords: 1, 0}{String Coords: 2, 0}{String Coords: 3, 4} {String Coords: 0, 0}{String Coords: 1, 0}{String Coords: 2, 1}{String Coords: 3, 0} ... {String Coords: 0, 4}{String Coords: 1, 4}{String Coords: 2, 6}{String Coords: 3, 4}

Pretty cool if you want to visualize what is going on.

You shouldn't use Aggregate to build strings. You end up creating lots of intermediate strings that aren't needed. And the use of a SB is way more verbose than is needed. Just use string.Concat. RenderString can be implemented as return string.Concat(cp.Select(s=>string.Concat(s)+"\n")); and it'll be shorter, clearer, and pretty dramatically more efficient in both time and memory.

extremeandy · Accepted Answer · 2019-08-29 00:13:19Z

Here's a more procedural approach that is horrible to read, but is about twice as fast as Eric Lippert's suggestion.

static IReadOnlyList<IReadOnlyList<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences) { var arrays = sequences.Select(s => s.ToArray()).ToArray(); var numColumns = arrays.Length; if (numColumns == 0) { return new[] { Array.Empty<T>() }; } var arrayLengths = arrays.Select(l => l.Length).ToArray(); var arrayIndices = new int[numColumns]; var numRows = arrayLengths.Aggregate((x, y) => x * y); var lastColumnIndex = numColumns - 1; var combinations = new IReadOnlyList<T>[numRows]; for (var rowIndex = 0; rowIndex < numRows; rowIndex++) { var items = new T[numColumns]; for (var columnIndex = 0; columnIndex < numColumns; columnIndex++) { items[columnIndex] = arrays[columnIndex][arrayIndices[columnIndex]]; } combinations[rowIndex] = items; for (var i = lastColumnIndex; i >= 0; i--) { var updatedIndex = arrayIndices[i] = (arrayIndices[i] + 1) % arrayLengths[i]; if (updatedIndex > 0) { break; } } } return combinations; }

Collectives™ on Stack Overflow

Possible combinations

3 Answers 3

3 Comments

1 Comment

Comments

Linked

Hot Network Questions