再びトーナメント表作成 ③ 順番をランダムに並べ替えたい－１

昨日はトーナメント表作成において、なるべく全大会の入賞者が初戦で
ぶつからないよう、良い感じに分散させることに挑戦した。
infoment.hatenablog.com
しかしそうは言っても、完全ランダムで配置したいこともあるだろう。
ということで今日は、配列をランダムに並べ替えることに挑戦する。

実は今までにも、何度か挑戦したことがあった。そのときの作戦はこうだ。
例）1～32をランダムな順序で配列に格納したい。

1. 辞書２を作成する。辞書２のkeyおよびitemには順に1～32をセットしておく。
2. 1～32の数字を乱数で作成する。
3. 作成した数字が辞書２のキーに存在するか、評価する。存在する場合、辞書１のkeyにセットする。このとき、itemの値は不問。
4. 上記でセットしたkeyの値を、辞書２のkeysからRemoveする。
5. 繰り返し（２. へ戻る）

これにより、どの数字が使われたか、使われていないかが判るという理屈。
最初の内は乱数の生成結果が重複することはまれだが、後半になるにつれ
何度も乱数生成を要する確率が上がっていくことになる。
↓ 実際試してみると、このケースでは合計で93回も乱数を生成している。

同じケースを1000回繰り返し、乱数生成の合計平均を求めた結果は、
約130回であった。やはり、結構かかってしまう。

そこで、もっと時間が掛からない方法はないものかと考えて、行きついた
結果がこちら。
例）1～32をランダムな順序で配列に格納したい。

1. １～32の各々に、乱数「１～100」×100を乗じて足し算する。
2. 足し算した結果を昇順（または降順）ソートする。
3. ソートされた順に、下二桁を取り出して配列に格納する。

↓ まず並べ替え用の数を足して、

↓これを並べ替えて、下二桁を抽出。

並べ替えは後から加えたランダムな数が優先される一方で、下二桁は元の数字が
保存されているので、これでランダム並べ替えが成立するという仕組みだ。

と、ここで時間切れ。明日に続きます。

参考まで。