c# - 列出排列（未知数）

Question

可能重复：
List<List<int>> 的组合

我有多个列表，可以是 2 个或 3 个最多 10 个列表，其中包含多个值。现在我需要做的是获得所有这些的组合。

例如，如果我有 3 个具有以下值的列表：

• 清单 1：3、5、7
• 清单 2：3、5、6
• 清单 3：2、9

我会得到这些组合

• 3,3,2
• 3,3,9
• 3,5,2等..

现在的问题是我不能轻易做到这一点，因为我不知道我有多少个列表，因此确定我需要多少个循环。

Answer 1

您可能可以使这变得容易得多，但这就是我刚才的想法：

List<List<int>> lists = new List<List<int>>();
lists.Add(new List<int>(new int[] { 3, 5, 7 }));
lists.Add(new List<int>(new int[] { 3, 5, 6 }));
lists.Add(new List<int>(new int[] { 2, 9 }));

int listCount = lists.Count;
List<int> indexes = new List<int>();
for (int i = 0; i < listCount; i++)
    indexes.Add(0);

while (true)
{
    // construct values
    int[] values = new int[listCount];
    for (int i = 0; i < listCount; i++)
        values[i] = lists[i][indexes[i]];

    Console.WriteLine(string.Join(" ", values));

    // increment indexes
    int incrementIndex = listCount - 1;
    while (incrementIndex >= 0 && ++indexes[incrementIndex] >= lists[incrementIndex].Count)
    {
        indexes[incrementIndex] = 0;
        incrementIndex--;
    }

    // break condition
    if (incrementIndex < 0)
        break;
}

如果我没有完全错，这应该是列表O(Nm)的数量和排列的数量（所有列表长度的乘积）。mNm

Answer 2

你可以制作一个List<List<yourValueType> mainlist你所有的清单。然后用一个简单的

int numberOfIterations = 1;
foreach(var item in mainlist)
{
    numberOfIterations *= item.Count;
}

这将获得您总共必须执行的迭代次数。

Answer 3

非递归解决方案，适用于任何IEnumerables（不仅仅是列表）而不固化它们：

public static IEnumerable<IEnumerable<T>> Permutations<T>(
    this IEnumerable<IEnumerable<T>> source)
{
    // Check source non-null, non-empty?

    var enumerables = source.ToArray();
    Stack<IEnumerator<T>> fe = new Stack<IEnumerator<T>>();
    fe.Push(enumerables[0].GetEnumerator());

    while (fe.Count > 0)
    {
        if (fe.Peek().MoveNext())
        {
            if (fe.Count == enumerables.Length)
                yield return new Stack<T>(fe.Select(e => e.Current));
            else
                fe.Push(enumerables[fe.Count].GetEnumerator());
        }
        else
        {
            fe.Pop().Dispose();
        }
    }
}

Answer 4

作为替代方案，遵循 rawlings 的一般想法，以下应该有效

public static IEnumerable<IEnumerable<T>> Permutations<T> (this IEnumerable<IEnumerable<T>> underlying)
{
    var enumerators = new Queue<IEnumerator<T>>(underlying.Select(u => u.GetEnumerator())
                                                          .Where(enumerator => enumerator.MoveNext());
    Boolean streaming = enumerators.Any();
    if(streaming)
    {
        IEnumerable<T> result;

        IEnumerator<T> finalEnumerator = enumerators.Dequeue();
        Func<Boolean,Boolean> finalAction = b => b ? b : finalEnumerator.MoveNext();

        Func<Boolean,Boolean> interimAction = 
         enumerators.Reverse()
                    .Select(enumerator => new Func<Boolean,Boolean>(b => b ? b : (enumerator.MoveNext() ? true : enumerator.ResetMove())))
                    .Aggregate((f1,f2) => (b => f1(f2(b)));
        enumerators.Enqueue(finalEnumerator);

        Func<Boolean,Boolean> permutationAction = 
                              interimAction == null ? 
                              finalAction :
                              b => finalAction(interimAction(b));

        while(streaming)
        {
              result = new Queue<T>(enumerators.Select(enumerator => enumerator.Current))
              streaming = permutationAction(true);
              yield return result;
        }
}

private static Boolean ResetMove<T>(this IEnumerator<T> underlying)
{
     underlying.Reset();
     underlying.MoveNext();
     return false;
}

Answer 5

不是很有效但很容易理解的方法可能是递归地解决这个任务。考虑一种计算N个列表的排列的方法。如果您有这样的方法，那么您可以通过将N个列表的所有排列与最后一个列表中的每个数字相结合来轻松计算N+1 个列表的排列。您还应该处理0列表排列的极端情况。然后实现似乎很简单：

IEnumerable<IEnumerable<T>> GetAllPermutations<T>(IEnumerable<IEnumerable<T>> inputLists)
{
    if (!inputLists.Any()) return new [] { Enumerable.Empty<T>() };
    else
    {
        foreach (var perm in GetAllPermutations(inputLists.Skip(1)))
            foreach (var x in inputLists.First())
                yield return new[]{x}.Concat(perm);
    }
}