C#でサイズnの順列をすべて生成したい。

サイズ$n$の順列をすべて生成する処理をC#で実装する機会があったので、そのメモになります。RubyやPythonだと順列の列挙は標準ライブラリに用意されており、ふだんはそういう「出来合い」のものを使うことが多いので、自力で実装するのに思ったよりも時間がかかってしまった(´・ω・｀)

using System;
using System.Collections.Generic;
using System.Linq;

namespace permutations
{
    class Program
    {
        static List<List<T>> Permutations<T>(List<T> src, int n)
        {
            // nは1以上かつsrcの長さよりも短い必要がある。
            int len = src.Count;
            if (!(0 < n && n <= len))
            {
                throw new ArgumentOutOfRangeException();
            }

            var permutations = new List<List<T>>();
            var queue = new Queue<List<int>>(Enumerable.Range(0, len).Select(i => new List<int>() { i }));
            while (queue.Any())
            {
                var indexes = queue.Dequeue();

                if (indexes.Count == n)
                {
                    permutations.Add(indexes.Select(index => src[index]).ToList());
                    continue;
                }

                for (int index = 0; index < len; index++)
                {
                    if (indexes.Contains(index))
                    {
                        continue;
                    }

                    var newIndexes = new List<int>(indexes);
                    newIndexes.Add(index);
                    queue.Enqueue(newIndexes);
                }
            }

            return permutations;
        }
    }
}

• インターネットの広大な海で調べてみると、再帰を利用して実装している例が多かったのですが、今回はQueueを使った幅優先探索にしてみました。再帰は実装がシンプルになる反面、深くなるとStack Over Flowなどの制御が難しくなるため、個人的にはStackやQueueを使うほうが個人的には好みです。
• 生成した順列をすべてリストに格納するため、順列の数が多くなると、それだけメモリの消費量が多くなります。つまり順列の数が多くなることが明らかな場合、上記のような実装では注意が必要です。本来ならばyield returnやイテレータなどを利用し、メモリの消費量を制限すべきですが、自分が使う分には問題ないので、よしとします(´・ω・｀)

最後に使用方法を2つ示して終わりにしたいと思います。まずひとつめ。

var src = new List<string>() { "A", "B", "C", "D", "E" };
var permutations = Permutations(src, 3);
for (int i = 0; i < permutations.Count; i += 5)
{
    int j = Math.Min(i + 4, permutations.Count);
    var tokens = permutations.GetRange(i, j - i + 1).Select(permutation => "[" + string.Join(",", permutation) + "]");
    var line = string.Join(" ", tokens);
    Console.WriteLine(line);
}

これを実行すると、以下のような値が標準出力に出力されます。

[A,B,C] [A,B,D] [A,B,E] [A,C,B] [A,C,D]
[A,C,E] [A,D,B] [A,D,C] [A,D,E] [A,E,B]
[A,E,C] [A,E,D] [B,A,C] [B,A,D] [B,A,E]
[B,C,A] [B,C,D] [B,C,E] [B,D,A] [B,D,C]
[B,D,E] [B,E,A] [B,E,C] [B,E,D] [C,A,B]
[C,A,D] [C,A,E] [C,B,A] [C,B,D] [C,B,E]
[C,D,A] [C,D,B] [C,D,E] [C,E,A] [C,E,B]
[C,E,D] [D,A,B] [D,A,C] [D,A,E] [D,B,A]
[D,B,C] [D,B,E] [D,C,A] [D,C,B] [D,C,E]
[D,E,A] [D,E,B] [D,E,C] [E,A,B] [E,A,C]
[E,A,D] [E,B,A] [E,B,C] [E,B,D] [E,C,A]
[E,C,B] [E,C,D] [E,D,A] [E,D,B] [E,D,C]

2つ目のサンプルはもうちょっとシンプルです。

var src = new List<int>() { 1, 2, 3, 4 };
foreach (var permutation in Permutations(src, 2))
{
    Console.WriteLine(string.Join(",", permutation));
}

この実行結果は次の通りです。

1,2
1,3
1,4
2,1
2,3
2,4
3,1
3,2
3,4
4,1
4,2
4,3