こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

締切り済みの質問

N個の整数の並び替えるアルゴリズム

N個の整数1,2,3,...Nから任意のM個(M < N )を取り出すのですが、重複はダメという場合、どのようなアルゴリズムがあるでしょうか。重複ありなら、Nまでの一様乱数を発生させて整数化して取り出すことは可能です。今回は重複なしです。重複があったらやり直して重複なしになるまでやり続けるというのはダメだなと思っています。
データ処理言語のRはコマンド1つのようですが。言語はFortranなのですが、アルゴリズムのレベルだとどれでも同じと考えています。よろしくお願いします。

投稿日時 - 2020-05-12 01:04:39

QNo.9747470

すぐに回答ほしいです

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(4)

ANo.4

f272さんが紹介しているのは、Fisher–Yates shuffle ですね。

Wikipediaにもありますが、実装さえ間違えなければ大丈夫です。

投稿日時 - 2020-05-12 18:17:13

お礼

回答ありがとうございました。標準のアルゴリズムのようですね。
たぶん、python, Rなどのライブラリは間違いのないものが実装されていてそのような個別パーツは自分で考えて作り出すのではなく、出来上がっている間違いのないものを使うべきだということではないかと思います。Fortranにもそういうライブラリ集があるのでしょうか。大昔からテキストに載っているようなものの以外にですが。

投稿日時 - 2020-05-13 09:37:10

ANo.3

乱数発生が完全に一様であれば,このアルゴリズムですべての場合が等確率で出てきますから,これ以上よけいなことをする必要はありません。

投稿日時 - 2020-05-12 17:25:29

お礼

回答ありがとうございます。すでに実績のある標準アルゴリズムということですね。これをサブルーチン化して外部から呼び込めるようにしたいと思います。

投稿日時 - 2020-05-13 09:32:57

ANo.2

こんな感じ?
program test
implicit none
integer,parameter :: n=10
integer,parameter :: m=5
integer :: t, i, j
integer,dimension(n) :: ar=(/(i,i=1,n)/)
real :: rnd(n)
call random_number(rnd)
do i=n,2,-1
j=int(rnd(i)*i)+1
t=ar(i)
ar(i)=ar(j)
ar(j)=t
enddo
print*,(ar(i),i=1,m)
end program test

投稿日時 - 2020-05-12 02:04:23

お礼

回答ありがとうございます。このアルゴリズムは乱数に基づいた交換というシャッフルをカードの枚数回、しかもすべてのカードが必ずシャッフルの対象となるようにすればそのカードの先頭から順番に抜き出せば重複のないランダムな取り出しになっているということですね。
この場合、最初が順番どおりになっているので初期の影響が完全に消えるということをするため、再度シャッフル(2枚の交換)をした方がいいというようなことはないでしょうか。どこまでやると最初の条件の影響が消えていくのだろうと思いますが。案外すぐに消えるものでしょうか。

投稿日時 - 2020-05-12 15:22:33

ANo.1

ざっと、

今取り出した物aを、
既に取り出した物bと比較して、
a=bのとき、aを破棄する。

を、bがm個になるまで繰り返す。

投稿日時 - 2020-05-12 01:15:22

あなたにオススメの質問