技術者派遣の技術日誌ブログ

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

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

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

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

static List> AllPermutation(T[] nums) {

 if (nums.Length == 1) {

 List> list = new List>();

list.Add(new List { nums[0] });        return list;    }

else {        List subNum = nums.ToList();

subNum.RemoveAt(0);

List> sub = AllPermutation(subNum.ToArray());

 List> result = new List>();

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 AllPermutation(IEnumerable nums) {

 if (nums.Count() == 1) {        yield return new T[1] { nums.First() };    }

else {        IEnumerable subNum = nums.Skip(1);

var sub = AllPermutation(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を使うことになるのだろうか？