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

質問

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

回答No.4

pooh26

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

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

お礼

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

回答No.3

f272

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

お礼

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

回答No.2

f272

こんな感じ？
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

お礼

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

回答No.1

m5048172715

ざっと、

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

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