サットロのアルゴリズム

別段分ける必要もなかったんだけど、このシャッフルは別物として記事を分けてみた.
フィッシャー–イェーツのシャッフルにおいて、問題というほどではないが場合によっては困ることがある.

これは1回のシャッフルをやった後の結果である.
以前と同じ表示をするとこうだ.

選出|固定した
0 1 2 3 4 5 6 7 8 9 |
0 1 2 3 4 5 6 7 8 | 9 <=変わってない！！！！

そう、最大値が選ばれた場合は同じものが来る可能性があるのである！
最悪の場合は何も変わってない状態というのも、低い確率ではあるがあり得る.
これを解決するのがサットロのアルゴリズム.
やることは非常にシンプル,indexを弄るだけ.

    // Sattoloの実装
    auto Sattolo = [&]()
    {
        weightList.clear();
        weightList.push_back(dataList);

        for (int index = dataList.size() - 1; index > 0; index--)
        {
            int flip = Random(0, index - 1); // -1しとく
            std::swap(dataList[index].weight, dataList[flip].weight);

            weightList.push_back(dataList);
        }
    };

こうすることで現在のものが選ばれないので、絶対に入れ替わりが発生するようになる.
前回作ったツールをこれに置き換えて実行したら以下のような感じになった.

選出|選ばない|固定した

3つの境界に分離して考えると分かりやすいね.
毎回選ばないものが存在して、それと選出した中から交換をするので、絶対に同じ位置に来ることはない.
非常にシンプルだけど、同じ並びが来ないという前提が欲しい時は$-1$をしてあげてください.

---

1. フィッシャー–イェーツのシャッフル ↩