生成排列的LINQ代码的说明

Question

有人可以向我解释这段代码如何产生排列吗？

我看到它正在使用递归列表构建,但我不能完全了解精确的机制.

public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> list)
{
    if (list.Count() == 1)
        return new List<IEnumerable<T>> { list };
    return list
        .Select((a, i1) => 
                    Permute(list.Where((b, i2) => i2 != i1))
                   .Select(b => (new List<T> { a }).Union(b)))
        .SelectMany(c => c);
}

Answer 1

首先,我要指出这依赖于Union未指定的排序,并且只有在原始集合中的值是唯一的情况下才有效.改变Union以Concat解决这个问题.

我怀疑它的价格也非常昂贵.无论如何...

你可以通过归纳来理解它.它绝对适用于单个元素集合,基于if.那么,让我们从那里开始吧.

假设我们假设它适用于这样的大小集合n:

{ e1, ... en }

现在让我们看看它是否适用于大小的集合n + 1.该调用将绕过"if",并进入递归返回部分.所以我们留下:

list.Select((a, i1) => 
                Permute(list.Where((b, i2) => i2 != i1))
               .Select(b => (new List<T> { a }).Union(b)))
    .SelectMany(c => c);

这SelectMany部分只是收集了一系列收藏品 - 这很简单.所以让我们关注这个Select电话.它说...

• 对于a原始集合中的每个元素(),我们知道它具有索引i1...
  • 计算出除该元素之外的列表(即list.Where(...)部分)
  • 对于那个较小的列表的每个排列(这是Permute调用)......
  • ...生成一个由元素组成的新列表,a后跟"当前排列"(这是new List(...).Union(b)部分.)

所以如果我们的集合是{x,y,z}我们会得到:

• 每个{ y, z }前缀的集合x
• 每个{ x, z }前缀的集合y
• 每个{ x, y }前缀的集合z

这几乎定义了"每个排列"......所以它适用于n + 1.

鉴于基本情况和归纳步骤,它因此适用于任何大于或等于1的大小的集合.