C#:全ての要素を使った順列を求める



## 全ての要素を使った順列を求める

たとえば、{ 1, 2, 3 } が与えられた場合は、与えられた要素をすべてつかった順列は、

<pre>
{ 1, 2, 3 } 
{ 1, 3, 2 } 
{ 2, 1, 3 } 
{ 2, 3, 1 } 
{ 3, 1, 2 } 
{ 3, 2, 1 } 
</pre>

の６通りが求められます。

順列は、見方を変えると、Tree構造になっていますので、基本的にTreeを辿るのと同じ構造でプログラムが書けます。つまり再帰処理が使えるってことですね。

## 順列を求めるC#のコード (First Version)

以下に示すのが、最初に作成したC#のコードです。

```csharp
class Program {
    static void Main(string[] args) {
        // 確認用コード
        var perm = new Permutation();
        foreach (var n in perm.Enumerate(new[] { 1, 2, 3, 4 })) {
            foreach (var x in n)
                Console.Write("{0} ", x);
            Console.WriteLine();
        }
        Console.ReadLine();
    }
}

public class Permutation {
    public IEnumerable<T[]> Enumerate<T>(IEnumerable<T> items) {
        return _GetPermutations<T>(new List<T>(), items.ToList());
    }

    private IEnumerable<T[]> _GetPermutations<T>(IEnumerable<T> perm, IEnumerable<T> items) {
        if (items.Count() == 0) {
            yield return perm.ToArray();
        } else {
            foreach (var item in items) {
                var result = _GetPermutations<T>(perm.Concat(new T[] { item }),
                                                    items.Where(x => x.Equals(item) == false)
                                );
                foreach (var xs in result)
                    yield return xs.ToArray();
            }
        }
    }
}
```

ジェネリックメソッドにしていますので、要素の型は、int以外の任意の型にも対応できます。

メインとなるのは、Enumerateメソッドの下請けである _GetPermutationsメソッドです。このメソッドで再帰処理をしています。
第1引数には、現在注目している順列がわたります。再帰するたびに、この順列に、ひとつ要素が加わります。
第2引数には、まだ使われていない数のリストが渡ります。こちらは、再帰呼び出しされるたびに、ひとつずつ要素が減っていきます。このリストが空になったら、ひとつの順列が求まったので、`yield return` で結果を返しています。
第2引数のリストが空でない場合は、これまで求まった順列に、第2引数のリストの要素を一つ後ろに加えて、_GetPermutationsメソッドを再帰的に呼び出しています。


## 別の視点でコードを書いてみる

最初に書いたコードは、２つのメソッドに分かれているのがどうも気に入りません。そこで順列について再考。

{1, 2, 3}の3つの要素からすべての要素を取り出す(重複を許さない)順列を考えます。
求める順列は、1が先頭に来るもの、2が先頭に来るもの、3が先頭に来るものの3つのパターンがあります。

<pre>
{1, x, y}
{2, x, y}
{3, x, y}
</pre>

という3つです。
{1, x, y}の場合について考えてみると、1を除いた{2,3}から生成される順列が、x,yに当たるわけですから、

<pre>
 {1} + {2,3}から得られる順列
</pre>

を求めればよいことになります。つまり、再帰処理が書けます。なお、集合の要素がひとつだったら、その要素だけの順列を返せばよいので、ここで再帰処理が終わります。

## 順列を求めるC#のコード (2nd Version))

これをコードに落としたのが、次のコードです。

```csharp
public IEnumerable<T[]> Enumerate<T>(IEnumerable<T> items) {
    if (items.Count() == 1) {
        yield return new T[] { items.First() };
        yield break;
    }
    foreach (var item in items) {
        var leftside = new T[] { item };
        var unused = items.Except(leftside);
        foreach (var rightside in Enumerate(unused)) {
            yield return leftside.Concat(rightside).ToArray();
        }
    }
}
```

コードは、[GitHub](https://github.com/gushwell/CSharpAlgorithmCollection)で公開しています。
こちらのほうが理解しやすいかな。速度もこちらのほうが、速くなっているようです。

ところで、内側のforeachの中でToArrayを呼び出していますが、これをしないと遅くなってしまいます。再帰的メソッド　+ yield return + LINQ to Objects使う際に注意しないといけない部分かと思います。


## 実行結果

最初に示した確認用コードを実行した結果です。
1,2,3,4すべてをつかった順列を列挙しています。

```
1 2 3 4 
1 2 4 3 
1 3 2 4 
1 3 4 2 
1 4 2 3 
1 4 3 2 
2 1 3 4 
2 1 4 3 
2 3 1 4 
2 3 4 1 
2 4 1 3 
2 4 3 1 
3 1 2 4 
3 1 4 2 
3 2 1 4 
3 2 4 1 
3 4 1 2 
3 4 2 1 
4 1 2 3 
4 1 3 2 
4 2 1 3 
4 2 3 1 
4 3 1 2 
4 3 2 1 
```
-------------------------
この記事は、Gushwell's C# Programming Pageで公開したものを加筆・修正したものです。