Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

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

たとえば、{ 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();
        }
    }
}

コードは、GitHubで公開しています。
こちらのほうが理解しやすいかな。速度もこちらのほうが、速くなっているようです。

ところで、内側の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で公開したものを加筆・修正したものです。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした