全ての要素を使った順列を求める
たとえば、{ 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すべてをつかった順列を列挙しています。
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で公開したものを加筆・修正したものです。