如何迭代具有不同长度的列表以找到所有排列？ [英] How to iterate lists with different lengths to find all permutations?

问题描述

这应该不太难，但是我的脑子似乎有一个堆栈溢出（色调）。我有一系列列表，我想找到它们可以排序的所有排列。所有列表的长度都不同。

This one should not be too hard but my mind seems to be having a stack overflow (huehue). I have a series of Lists and I want to find all permutations they can be ordered in. All of the lists have different lengths.

例如：

清单1：1

清单2：1、2

所有排列都是：

1，1

1、2

就我而言，我不会切换数字。 （例如2，1）
最简单的写法是什么？

In my case I don't switch the numbers around. (For example 2, 1) What is the easiest way to write this?

推荐答案

我不能说如果以下是最简单的方法，但IMO是最有效的方法。这基本上是我对每个答案的回答的概括版本锯齿状数组中的组合：

I can't say if the following is the easiest way, but IMO it's the most efficient way. It's basically a generalized version of the my answer to the Looking at each combination in jagged array:

public static class Algorithms
{
    public static IEnumerable<T[]> GenerateCombinations<T>(this IReadOnlyList<IReadOnlyList<T>> input)
    {
        var result = new T[input.Count];
        var indices = new int[input.Count];
        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);
        }
    }
}

您可以在链接的答案（不久它就是模拟嵌套循环）。同样，由于出于性能方面的原因，它会产生不克隆它的内部缓冲区，因此，如果要存储结果供以后处理，则需要对其进行克隆。

You can see the explanation in the linked answer (shortly it's emulating nested loops). Also since for performace reasons it yields the internal buffer w/o cloning it, you need to clone it if you want store the result for later processing.

示例用法：

var list1 = new List<int> { 1 };
var list2 = new List<int> { 1, 2 };
var lists = new[] { list1, list2 };

// Non caching usage
foreach (var combination in lists.GenerateCombinations())
{
    // do something with the combination
}

// Caching usage
var combinations = lists.GenerateCombinations().Select(c => c.ToList()).ToList();

更新： GenerateCombinations 是标准的C＃ iterator 方法，其实现基本上模拟 N 嵌套循环（其中 N 是输入。计数）像这样（用伪代码）：

UPDATE: The GenerateCombinations is a standard C# iterator method, and the implementation basically emulates N nested loops (where N is the input.Count) like this (in pseudo code):

for（int i ₀ = 0; i ₀ < input [0] .Count; i ₀ ++）

for（int i ₁ = 0; i ₁ < input [1] .Count; i ₁ ++）

for（int i ₂ = 0 ; i ₂ < input [2] .Count; i ₂ ++）

...

为（ int i _N-1 = 0; i _N-1 < input [N-1] .Count; i _N-1 ++ ）

yield {输入[0] [i ₀ ]，输入[1] [i ₁ ]，输入[2] [i ₂ ]，...，输入[N-1] [i _N-1 ]}

for (int i₀ = 0; i₀ < input[0].Count; i₀++)
for (int i₁ = 0; i₁ < input[1].Count; i₁++)
for (int i₂ = 0; i₂ < input[2].Count; i₂++)
...
for (int i_N-1 = 0; i_N-1 < input[N-1].Count; i_N-1++)
yield { input[0][i₀], input[1][i₁], input[2][i₂], ..., input[N-1][i_N-1] }

或以其他方式显示它：

for (indices[0] = 0; indices[0] < input[0].Count; indices[0]++)
{
    result[0] = input[0][indices[0]];
    for (indices[1] = 0; indices[1] < input[1].Count; indices[1]++)
    {
        result[1] = input[1][indices[1]];
        // ...
        for (indices[N-1] = 0; indices[N-1] < input[N-1].Count; indices[N-1]++)
        {
            result[N-1] = input[N-1][indices[N-1]];
            yield return result;
        }
    }
}

这篇关于如何迭代具有不同长度的列表以找到所有排列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！