的&QUOT每个组合;从每个n集合&QUOT的1项; [英] Every combination of "1 item from each of N collections"

问题描述

我有一个嵌套的列表<名单< INT>> 的数据结构，我想遍历内心深处的每一个可能的组合 INT 元素，如在每个组合由每个内部一个值列表< GT INT&; 被使用。例如，请考虑以下嵌套列表：

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
...

我怎么能做到这一点

我最初的做法是使指数排列，但长度内列表< INT> 列表不一定是相等的。我能想到的另一种方法是相乘的长度每个内部列表< INT> ，然后使用模和除法运算符与Math.Floor结合，以确定指标，但我不知道如何确切时间 N 的集合都存在实现这一点的。

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.

推荐答案

我已经回答了几个类似的问题，而这一切基本上使用一个的变化和相同的算法。这里是的修改后的版本在锯齿形阵列中的每个组合展望：

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

请注意，为了不做分配，上述方法产生一个和相同阵列的实例。如果你只想计数或的foreach 循环或LINQ查询处理它没有存储结果，这是完美的。例如：

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
}

的东西

如果您确实需要存储的结果，可以随时使用了ToList ：

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

这篇关于的&QUOT每个组合;从每个n集合&QUOT的1项;的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！