【C#】pythonのitertools.permutationsをC#で書いてみた。

python なら 簡単に順列の表現ができる・・・が、C#ではどうやってやるんだ？と 考えてもよくわからなかったので、python のitertools.permutationsの内容をC#で置き換えてみた。

pythonのコードはこちらに記載されている。 https://docs.python.org/3/library/itertools.html#itertools.permutations

def permutations(iterable, r=None):
    # permutations('ABCD', 2) → AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) → 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

このpermutationsに引数を与えると、順列の結果が返ってくる。 これをC#で書くとどうなるのか・・・を書いてみました。

internal class Program
{
    public static void Main(string[] args)
    {
        var a = Permutation("ABCDE", 4);
        List<string> result = new List<string>();
        foreach (var b in a)
        {
            string str = "";
            foreach (var c in b)
            {
                str += c.ToString();
            }
            result.Add(str);
        }

        
        Console.WriteLine(result.Count);
    }

    /// <summary>
    /// Permutation 順列(重複あり)
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="iterable">葉入れ悦</param>
    /// <param name="r">nPr の rの部分</param>
    /// <returns></returns>
    static IEnumerable<IEnumerable<T>> Permutation<T>(IEnumerable<T> iterable, int r = -1)
    {
        //入力を配列に変更
        var pool = iterable.ToList();
        //配列の長さ
        int n = pool.Count;

        r = r < 0 ? n : r;
        //総数より、抽出が大きい場合は終了
        if (r > n) yield break;
        /*全長*/
        var indices = Enumerable.Range(0, n).ToList();
        /*後ろから*/
        var cycles = Enumerable.Range(n - r + 1, r).ToList();
        cycles.Reverse();
        //変化なし版
        yield return indices.Take(r).Select(i => pool[i]);

        int indicesLength = indices.Count;
        int cyclesLength = cycles.Count;

        while (true)
        {
            bool breakCheck = false;
            for (int i = r - 1; i >= 0; i--)
            {
                cycles[i] -= 1;
                if (cycles[i] == 0)
                {
                    /*iの値を最後尾に持っていき、i以降をひとつ前に寄せる*/
                    var tmp = indices[i];
                    for (int k = i; k < indicesLength - 1; k++)
                    {
                        indices[k] = indices[k + 1];
                    }
                    indices[indicesLength - 1] = tmp;
                    cycles[i] = n - i; // 順列でとる値を復活(元に戻す)
                    /*
                     * 確認のための出力
                    foreach (var c in indices)
                    {
                        Console.Write(c);
                    }
                    Console.Write("  ");

                    foreach (var p in cycles)
                    {
                        Console.Write(p);
                    }
                    Console.WriteLine(" ★");
                    */

                }
                else
                {
                    /*指定の番号との入れ変え*/
                    int j = cycles[i];
                    var tmp = indices[i];
                    // C# 8.0 空しか ^を利用したindexの表現はできないらしい。
                    //indices[i] = indices[indicesLength - j];
                    indices[i] = indices[^j];
                    indices[^j] = tmp;
                    /* 確認用
                    foreach(var c in indices)
                    {
                        Console.Write(c);
                    }
                    Console.Write("  ");

                    foreach(var p in cycles)
                    {
                        Console.Write(p);
                    }

                    Console.WriteLine();
                    */
                    yield return indices.Take(r).Select(i => pool[i]);
                    breakCheck = true;
                    break;
                }
            }
            if (!breakCheck) yield break;
           //yield break;
        }
    }

}

きれいなコードではないと思うが、これでいける。 これで何をしているのか…なのだが、 元の指定した配列を並び替え、前から数分だけ、出力するということをしている。 数学で nPr ように習ったあれである。

ここで利用しているindices と cyclesの遷移例です。 n = 5 , r = 3 とした場合の移り変わりになります。 https://drive.google.com/file/d/1PYs53PWsHqpG0NQSjsvJy2GQ_zFxFK4h/view?usp=drive_link

cyclesの後ろから、値が、3,2,1,0 と0になったら、一つ前のインデックスに移り、インデックスの値を3に戻し、再度処理を実施する。

また、インデックスの値が 0 以外の場合は、指定の場所を基準に値の入れ替え。インデックスの値が0 の場合は　指定の値をindicesの最後尾に配置し、指定の値以降の配列を一つずつ前に寄せる。

すると、すべてのパターンの並びの計算が可能というわけである。

書いてみたもののpythonより、若干読みにくいのかな。 というのと、rangeに関する仕様の違いやyield、Enumerableの扱いを普段やったことがなかったので、置き換えるのに時間がかかった。

ビジネスアプリ内のドメイン知識に対する処置とは違って、純粋に数式の計算のロジックは難しい・・・。