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

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

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

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

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

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

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

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

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

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

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

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

参考まで。