いつクリはてブロ

いつになったらクリエイティブするの?

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版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?


まずはこの辺を一から読み込んでみよう…。


※追記
RubyならArray#shuffle使えばいいのでは」という指摘がありました。
擬似コードとしてRubyで書きましたが、元々これを要求されたのがC使用時だったので、書こうと思ったけど書きませんでした。
Ruby便利ですね。