【C#】順列の列挙

競プロっぽいイメージがあるけど、普通の世界でも使いたくなる順列の列挙について。

C#での実装を検索すると様々あるが、Kzrnm氏のNextPermutation()、それをイテレーター化したPermutations()が良いと思った。

配列の切り貼りやリスト操作といった方法で実現するものも見つかるけれど、上記はスワップにて行うため省アロケーションで高速。

参考元のコードをそのまま転載するのもアレなので、内容消化の写経ついでにIComparisonOperators<TSelf, TOther, TResult>版とした NextPermutation を以下に折りたたむ。

IComparisonOperators<TSelf, TOther, TResult>版
（本来引用や参照で済むところなので折りたたみ）

public static bool NextPermutation<T>(Span<T> span)
    where T : IComparisonOperators<T, T, bool>
{
    int len = span.Length;
    int i = len - 2;

    while(i >= 0)
    {
        if (span[i] < span[i + 1]) break;
        i--;
    }
    if (i < 0) return false;

    int j = len - 1;
    do
    {
        if (span[i] < span[j]) break;

    } while (--j >= 0);

    (span[i], span[j]) = (span[j], span[i]);
    span.Slice(i + 1, len - i - 1).Reverse();

    return true;
}

4P4 で使ってみる。

var n = 4;
var array = Enumerable.Range(1, n).ToArray();
var span = array.AsSpan();

Console.Write(span.ToListString(" ")); // 載せないが ToListString() という拡張メソッドがあるものとする
while(NextPermutation(span))
{
    Console.Write($" {span.ToListString(" ")}");
}

// 結果
// [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]

空処理で n = 4, n = 10 として計測。（単位が違うので分けた）

          Method | n |     Mean |   Error |  StdDev |   Gen0 | Allocated |
---------------- |-- |---------:|--------:|--------:|-------:|----------:|
 NextPermutation | 4 | 209.6 ns | 2.57 ns | 0.14 ns | 0.0253 |      80 B |

          Method |  n |     Mean |    Error |   StdDev | Allocated |
---------------- |--- |---------:|---------:|---------:|----------:|
 NextPermutation | 10 | 30.99 ms | 26.19 ms | 1.435 ms |     123 B |

列挙だけなら N が増えてもアロケが最初に用意する配列ぶんだけなのがときめきポイント。

上記は std::next_permutation 的だけれど、イテレーターとして扱いたいとなれば参考元の Permutations()。
これについては、列挙にインデックスの順列を用いるのでTに制約がない。

以下は、 r を用いるなどして書いたものを折りたたみ。

r を用いるなどした Permutations() 折りたたみ

public static IEnumerable<T[]> Permutations<T>(T[] array, int? r = default)
{
    // 省略：用途に応じて Length = 0 や r が不正の場合などに yield break したり例外を飛ばす

    int ri = r ?? array.Length;

    int[] indices = Enumerable.Range(0, array.Length).ToArray();
    do
    {
        T[] result = new T[ri];
        for (int i = 0; i < result.Length; ++i) result[i] = array[indices[i]];

        yield return result;

    // 後述
    } while (NextPartialPermutation(indices.AsSpan(), ri));
}

foreachするなり LINQ するなり。

var cities = new string[] { "東京", "大阪", "名古屋", "福岡" };
var r = 2;
Console.WriteLine(string.Join(" ",
    Permutations(cities, r)
        .Select(v => v.ToListString(" → "))));

// 結果
// [東京 → 大阪] [東京 → 名古屋] [東京 → 福岡] [大阪 → 東京] [大阪 → 名古屋] [大阪 → 福岡] [名古屋 → 東京] [名古屋 → 大阪] [名古屋 → 福岡] [福岡 → 東京] [福岡 → 大阪] [福岡 → 名古屋]

シレッと r を使っているが、next_permutation を部分的に適用することで nPr になる。
参考：「や」の字: [C++] next_combination() 書いてみた

public static bool NextPartialPermutation<T>(Span<T> span, int r)
    where T : IComparisonOperators<T, T, bool>
{
    // 省略：用途に応じて Length = 0 や r が不正の場合などに false を返したり例外を飛ばす

    span[r..].Reverse();
    return NextPermutation(span);
}

（成立する原理を飲み込めていないのでここでは深追いしない。）

やっていることはシンプルだけれど一応計測。
前述 Permutations を使って 10C8 と 128C2。とりあえず後者のほうが小さいはず。

       Method |   n | r |      Mean |      Error |    StdDev |       Gen0 |   Allocated |
------------- |---- |-- |----------:|-----------:|----------:|-----------:|------------:|
 Permutations |  10 | 8 | 85.772 ms | 10.5097 ms | 0.5761 ms | 32333.3333 | 99225.38 KB |
 Permutations | 128 | 2 |  4.568 ms |  0.4225 ms | 0.0232 ms |   164.0625 |   509.21 KB |

終わり。

てくメモ

trivial な notes

【C#】順列の列挙