這個產生排列的LINQ代碼的說明

有人可以向我解釋這個代碼如何工作，它產生排列？這個產生排列的LINQ代碼的說明

我看到它使用遞歸列表建設，但我不能完全得到解決的確切機制我的大腦。

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

來源

2012-10-04 Aaron Anodide

如果你關心效率，不要打擾學習這段代碼。 – SimpleVar

而且，除非我讀得太快，否則如果你關心準確性。按照定義，置換是無序的，而Union（一種集合操作）既忽略順序又消除重複項。 – phoog

我主要關心的是，我明白代碼的作用，但現在它怎麼做 –

首先，我想指出，這依賴於Union排序，這是不確定的，且僅當原來的集合中的值是唯一的工作。將Union更改爲Concat會解決該問題。

我懷疑它也是可怕的昂貴。無論如何...

你可以通過歸納瞭解它。它絕對適用於單個元素集合，基於if。那麼，我們從那裏開始。

假設我們要實現它適用於大小n的這樣一個集合的假設：

{ e1, ... en }

現在讓我們來看看它是否適用於大小n + 1的集合。該調用將繞過「如果」，並進入遞歸返回部分。因此，我們只剩下：

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-04 17:47:21

這個產生排列的LINQ代碼的說明

回答

相關問題