2008年12月18日

C#で順列を列挙する

  
1,2,3 という要素に対し、

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

とすべての順列を列挙するにはどうしたら良いのだろうか。

以下、試しに書いてみたコード。

static List<List<T>> AllPermutation<T>(T[] nums) {
    if (nums.Length == 1) {
        List<List<T>> list = new List<List<T>>();
        list.Add(new List<T> { nums[0] });
        return list;
    } else {
        List<T> subNum = nums.ToList();
        subNum.RemoveAt(0);
        List<List<T>> sub = AllPermutation<T>(subNum.ToArray());
        List<List<T>> result = new List<List<T>>();
        foreach (var x in sub) {
            for (int i = 0; i < x.Count() + 1; i++) {
                var temp = x.ToList();
                temp.Insert(i, nums[0]);
                result.Add(temp);
            }
        }
        return result;
    }
}

private static void Hoge() {
    int[] nums = { 1, 2, 3, 4, 5 };
    var r = AllPermutation(nums);
    foreach (var a in r) {
        foreach (var x in a)
            Console.Write(x);
        Console.WriteLine();
    }
}

たぶん、動いていると思う。
でも、数が多くなると、表示されるまで、間が開いてしまう。

やはりこういった時は、IEnumerableを戻り値にするほうがよさそうだ。
ついでに引数の型なども変更。

static IEnumerable<T[]> AllPermutation<T>(IEnumerable<T> nums) {
    if (nums.Count() == 1) {
        yield return new T[1] { nums.First() };
    } else {
        IEnumerable<T> subNum = nums.Skip(1); 
        var sub = AllPermutation<T>(subNum); 
        foreach (var x in sub) {
            for (int i = 0; i <= x.Count(); i++) {
                var temp = x.ToList();
                temp.Insert(i, nums.First());
                yield return temp.ToArray();
            }
        }
    }
}

このような再帰を使った場合、スタックオーバーフローが気になる。
でも、この手のコードを再帰を使わないで書く方法がわからない。
どうも、再帰なしで書くのが苦手だ。
Stackを使うことになるのだろうか?


この記事へのコメント
最新版に Make.Permutation てのを入れてみています.
ご参考までに.
http://d.hatena.ne.jp/NyaRuRu/20080115/p1

using System;
using Achiral;
using Achiral.Extension;
static class Program
{
static void Main(string[] args)
{
foreach (var seq in Make.Permutation(5))
{
seq.ForEach(Console.Write);
Console.WriteLine();
}
}
}

いくつかのクエリ演算子はネイティブにサポートしてあるので,例えば以下のように「[0,14]の並び替えの 1000000000000L 番目が欲しい」みたいなときに一瞬で計算できます.

Make.Permutation(15)
.Skip(1000000000000L)
.Take(1)
.SelectMany(seq => seq)
.ForEach(Console.Write);

Posted by NyaRuRu at 2008年12月19日 02:43
NyaRuRuさん
いつもありがとうございます。
毎度のことながらすぐには理解できない頭なので、(^^;
あとでじっくり研究させていただきます。
Posted by Gushwell at 2008年12月19日 08:59
 

この記事へのトラックバックURL