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

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

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


{ 1, 2, 3 } 
{ 1, 3, 2 } 
{ 2, 1, 3 } 
{ 2, 3, 1 } 
{ 3, 1, 2 } 
{ 3, 2, 1 }

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

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

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

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

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つのパターンがあります。


{1, x, y}
{2, x, y}
{3, x, y}

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


 {1} + {2,3}から得られる順列

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

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

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

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で公開しています。
こちらのほうが理解しやすいかな。速度もこちらのほうが、速くなっているようです。

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

実行結果

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

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