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

  • 0
    いいね
  • 0
    コメント

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

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

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

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

    順列は、見方を変えると、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メソッドを再帰的に呼び出しています。

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

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

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

    こちらのほうが理解しやすいかな。速度もこちらのほうが、速くなっているようです。

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


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