カードをシャッフルする話

🚨注意🚨

以下，Ruby入門二日目のド素人がコード書いてます．

問題

1からnまでの値がそれぞれ書かれた$n$枚のカードをシャッフルしてください．

解答例

• shuffleメソッドを使います．

cards = [*1..n]
cards.shuffle
p cards 

• randでsortします．

cards = [*1..n]
cards.sort_by!{rand}
p cards

• 登場する数字がユニークになるまでrandを振り続けます．（頭悪い）

cards = Set.new
loop do
  cards << rand(max)
  if cards.size >= n
    p cards
    break
  end
end

• fisher-yatesのシャッフルアルゴリズムを使います．

フィッシャー–イェーツのシャッフル (英: Fisher–Yates shuffle) は、有限集合からランダムな順列を生成するアルゴリズムである。言い換えると、有限列をランダムな別の（シャッフルされた）順序の有限列に並べ直す方法である。

cards = [*1..n]
len = cards.length - 1
c = 0
len.step(1, -1) do |i|
  r = rand(i)
  c += 1
  cards[i], cards[r] = cards[r], cards[i]
end
p cards

• 現実世界でカードを引く動作を考慮してそのままプログラムにします．

cards = [*1..n]
shuffled = []
n.times do
  idx = rand(cards.length)
  shuffled << cards[idx]
  cards.delete_at(idx)
end
p cards

• シャッフルした結果は$n!$通りなので，それを辞書式に並べた時のインデックスを引くことでシャッフルします．
  • randを一回しか使わないのがいい．

def factorial(number)
  number = 0 if number.nil?
  (1..number).inject(1,:*)
end

cards = [*1..n]
shuffled = []
r = rand(factorial(n))
(n-1).downto(1) do |i|
  quotient = r/factorial(i)
  excess = r%factorial(i)
  shuffled << cards.delete_at(quotient)
  r = excess
end
p shuffled