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, Jan 15 '14 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, Jan 15 '14 at 17:47
@JonofAllTrades That's only an option with a number of lists known at compile time. Here it's not. — Servy, Jan 15 '14 at 17:49
Possible solution is here http://stackoverflow.com/questions/545703/combination-of-listlistint — Hannan Hossain, Jan 15 '14 at 17:56
First string must be form first List, second string from second List and so on so "first", "fourth" correct, "fourth", "first" not correct — user2412672, Jan 15 '14 at 18:00
@Servy: Why? It's a very rare day that I know how long my arrays are at compile time! — , Jan 15 '14 at 18:12
@JonofAllTrades Yes, I know that. That's my point. For nested loops to work, you need to know the number of lists at compile time because you need a loop per list. Therefore, because the number of lists are *not* known at compile time, nested loops (at least, alone) is not a suitable means of solving the problem. — Servy, Jan 15 '14 at 18:13
@Servy: No, sorry, it's perfectly simple to loop through the data and put together all unique combinations. I slapped it together in six lines, it tests fine. I'd post an answer, but I think the OP needs to show a little effort before handing it to him. Perhaps I'm missing something in your objection? — , Jan 15 '14 at 18:24
@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, Jan 15 '14 at 18:27

score 5 · Answer 1 · answered Jan 15 '14 at 17:43

5

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

answered Jan 15 '14 at 17:43

Servy

202,030
26
332
449

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! – joe_coolish Jan 15 '14 at 18:43
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 Jan 16 '14 at 07:06
@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. – Servy Jan 16 '14 at 15:01

score 1 · Answer 2 · answered Jan 15 '14 at 18:41

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. — Servy, Jan 15 '14 at 18:45

extremeandy · Answer 3 · 2019-08-29T00:13:19.657

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

Possible combinations

3 Answers3

Linked