0

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

我看到它正在使用递归列表构建，但我无法完全了解确切的机制。

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

1 回答 1

6

首先，我要指出，这依赖于 的顺序Union，这是未指定的，并且仅在原始集合中的值是唯一的情况下才有效。更改Union为Concat将解决此问题。

我怀疑它也贵得吓人。反正...

你可以通过归纳来理解它。它绝对适用于基于if. 所以，让我们从那里开始吧。

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

{ e1, ... en }

现在让我们看看它是否适用于 size 的集合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 的集合。

于 2012-10-04T17:47:21.870 回答