Every combination of "1 item from each of N collections"

Question

I have a nested List<List<int>> data structure, and I would like to iterate over every possible combination of the inmost int elements, such as that in each combination exactly one value from each inner List<int> is used. For example, please consider the following nested list:

var listOfLists = new List<List<int>>()
{
    new List<int>() { 1, 2, 3, 4, 9 },
    new List<int>() { 0, 3, 4, 5 },
    new List<int>() { 1, 6 }
};

The first few combinations would yield:

1 0 1 // Indices: 0 0 0
1 0 6 // Indices: 0 0 1
1 3 1 // Indices: 0 1 0
1 3 6 // Indices: 0 1 1
2 0 1 // Indices: 1 0 0
2 0 6 // Indices: 1 0 1
2 3 1 // Indices: 1 1 0
...

How could I accomplish this?

My initial approach was to make permutations of indices, but the lengths of inner List<int> lists are not necessarily equal. Another approach I can think of is multiplying the length of each inner List<int>, then using the modulo and division operators combined with Math.Floor to determine indices, but I'm not sure how exactly this could be implemented when N collections are present.

And also: http://stackoverflow.com/questions/4423838/cartesian-product-n-x-m-dynamic-array — Robin Mackenzie, Jun 02 '16 at 12:53
(Corrected my link) https://ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/ — Matthew Watson, Jun 02 '16 at 12:56
In my defense considering duplicates, I did my attempts at researching the problem, but I was missing the right keywords. — John Weisz, Jun 02 '16 at 12:59

score 1 · Accepted Answer · edited May 23 '17 at 12:24

I've answered a several similar questions, which all basically use a variation of one and the same algorithm. Here is the modified version of the Looking at each combination in jagged array:

public static class Algorithms
{
    public static IEnumerable<T[]> GetCombinations<T>(this IReadOnlyList<IReadOnlyList<T>> input)
    {
        var result = new T[input.Count];
        var indices = new int[result.Length];
        for (int pos = 0, index = 0; ;)
        {
            for (; pos < result.Length; pos++, index = 0)
            {
                indices[pos] = index;
                result[pos] = input[pos][index];
            }
            yield return result;
            do
            {
                if (pos == 0) yield break;
                index = indices[--pos] + 1;
            }
            while (index >= input[pos].Count);
        }
    }
}

Note that in order to not do allocation, the above method yields one and the same array instance. This is perfect if you want just to count or process it with foreach loop or LINQ query without storing the results. For instance:

foreach (var combination in listOfLists.GetCombinations())
{
    // do something with the combination
}

If you indeed need to store the results, you can always use ToList:

var allCombinations = listOfLists.GetCombinations().Select(c => c.ToList()).ToList();

From a performance perspective, this seems really efficient. I'm still working on understanding every segment of this snippet, but am I right to assume that the order of elements in each of the resulting combinations always reflects the order of lists which were passed in? — John Weisz, Jun 02 '16 at 13:32
Correct. What about the understanding, basically the algorithm is the unrolled version of a nested `for` / `foreach` loop :). — Ivan Stoev, Jun 02 '16 at 13:42

score 0 · Answer 2 · answered Jun 02 '16 at 13:01

How about using LINQ?

var listOfLists = new List<List<int>>()
{
    new List<int>() { 1, 2, 3, 4, 9 },
    new List<int>() { 0, 3, 4, 5 },
    new List<int>() { 1, 6 }
};

var result = from l in listOfLists[0]
             from y in listOfLists[1]
             from z in listOfLists[2]
             select new List<int>()
             {
                 l,
                 y,
                 z
             };

This will of course only work for this specific list as there are 3 lists in your list of lists.

_"This will of course only work for this specific list"_ -- this is my issue, there can be an arbitrary number of `List` elements in the `List>` value. — John Weisz, Jun 02 '16 at 13:04

Every combination of "1 item from each of N collections"

2 Answers2

Linked