1からNまでの数字をランダムに並べ替えるアルゴリズム
たとえば、1,2,3,4という4枚のカードがあったとして、それをランダムで並べ替える、つまり2,3,1,4とか、3,4,2,1とかを得るアルゴリズム。
ゲームを作るときに割と高頻度で使う。
アルゴリズムは苦手というか、雑に実装して終わらせてしまいたい派なので、多分うまい書き方が他にあるだろうなあと思いつつも、こういう実装をしてしまう。
array = [1,2,3,4] 100.times do rnd1 = rand(4) rnd2 = rand(4) t = array[rnd1] array[rnd1] = array[rnd2] array[rnd2] = t end
トランプなど実世界で考えるとこんな感じだろうが、プログラム的にはどう見ても無駄が多い。
という相談をデキる後輩にしたところ、「こういうのはどうすか?」と返ってきたのがこちら。
array = [1,2,3,4] 3.times do |i| rnd = rand(4-i) t = array[i] array[i] = array[rnd+i] array[rnd+i] = t end
これなら交換は3回で済むし、乱数の幅が順列の計算式4!と一致していて美しい。
アルゴリズムができる人のコードを見ると自分のコードが途端に汚らしく見えてくる。
経験の差だとは思うが、こういうのをさっと考案できる人は純粋に羨ましい。
自分も精進しなければと思う。
プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?
- 作者: 秋葉拓哉,岩田陽一,北川宜稔
- 出版社/メーカー: マイナビ
- 発売日: 2012/01/28
- メディア: 単行本(ソフトカバー)
- 購入: 25人 クリック: 473回
- この商品を含むブログ (28件) を見る
まずはこの辺を一から読み込んでみよう…。
※追記
「RubyならArray#shuffle使えばいいのでは」という指摘がありました。
擬似コードとしてRubyで書きましたが、元々これを要求されたのがC使用時だったので、書こうと思ったけど書きませんでした。
Ruby便利ですね。