CODEWITHSUNDEEP
c#arrays
John Weisz
John Weisz

Reputation: 31992

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

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.

Upvotes: 2

Views: 401

Answers (2)

Ivan Stoev
Ivan Stoev

Reputation: 205769

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

Upvotes: 1

Mike Eason
Mike Eason

Reputation: 9713

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.

Upvotes: 0

Related Questions