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 }

それでは、サイズのコレクションで機能するかどうかを見てみましょう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 に答える