Edited at

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で公開したものを加筆・修正したものです。