スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

[Ruby][アルゴリズム入門]ランダムな順列

第一章「ウォーミングアップ」 目次

1-0 アルゴリズムとは
1-1 漸化式
1-2 写像
1-3 順位付け
1-4 ランダムな順列
1-5 モンテカルロ法
1-6 ユークリッドの互除法
1-7 エラトステネスのふるい

ランダムな順列

1~Nの値を1回使って出来るランダムな順列を作る。

トランプをシャッフルしたりするのに便利そう。
# encoding: cp932
N = 20

# 1~引数nの乱数を返す
def irand(n)
  return (rand(n) + 1)
end

a = Array.new(N + 1, 0)

a[1] = irand(N)
2..N.times do |i|
  begin
    a[i] = irand(N)
    flag = false
    for j in 1..(i - 1)
      if (a[i] == a[j])
        flag = true
        break
      end
    end
  end while flag
end

1..N.times do |i|
  print "#{a[i]} "
end


上記の改良

上記のアルゴリズムを改良した効率のよいアルゴリズムを考える。

# encoding: cp932
N = 20

# 1~引数nの乱数を返す
def irand(n)
  return (rand(n) + 1)
end

a = Array.new(N + 1){|i| i}

N.downto(2) do |i|
  j = irand(i - 1)
  a[j], a[i] = a[i], a[j]
end

a.each_with_index do |n, i|
  next if i == 0
  print "#{n} "
end

テーマ : プログラミング - ジャンル : コンピュータ

コメント
コメントの投稿
管理者にだけ表示を許可する

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。