順列をC#で（効率重視）

参照： 順列をC#で

元記事は関数型プログラミングのシンプルな実装をC#で再現したもので、決して効率的ではありません。

効率的にするには、たとえばHeapのアルゴリズム や、Johnson–Trotterのアルゴリズム、C++のstd::next_permutationで採用されている辞書順生成アルゴリズムなどがあります。

ここでは、Wikipediaに書かれたHeapのアルゴリズムをC#で書いてみましょう。

アロケーションをなるべく少なくするため、順列を IEnumerable<T> で列挙せず、あえて ReadOnlySpan<T> をコールバックで受け取る形にしてみました。

static void GeneratePermutation<T>(ReadOnlySpan<T> span, Action<ReadOnlySpan<T>> action)
{
    var n = span.Length;
    var buffer = new T[n];
    span.CopyTo(buffer);
    var c = new int[n];
    action(buffer);
    var i = 0;
    while (i < n)
    {
        if (c[i] < i)
        {
            var j = (i % 2 == 0) ? 0 : c[i];
            (buffer[i], buffer[j]) = (buffer[j], buffer[i]);
            action(buffer);
            c[i]++;
            i = 0;
        }
        else
        {
            c[i] = 0;
            i++;
        }
    }
}

GeneratePermutation<char>("abcd", span => Console.WriteLine(new string(span)));

オンラインでの実行例はこちら

---

参考（類似の記事）

• 置換(順列)の列挙