ランダム順列作成アルゴリズム

1からnまでの整数からm(<=n)個を選び出したい。ランダムに選び出すアルゴリズムを与えよ。

アルゴリズムなので、当然ながらいくつも存在しているわけですが。で、各アルゴリズムとそのオーダーについて。元ネタについては言及しません。
まず、オーダーがO(n*m)のアルゴリズムについて。

my @array;
for(1..$m){
     my $index = 0;
     my $select = int rand($n - $_ + 1) + 1;
     while($select){
         if(!$array[$index]){
             $select--;
         }
         $index++;
     }
     $index--;
     print $index + 1, "\n";
     $array[$index] = 1;
}

要素数nの配列を用意して、すでに使用されているものにチェックをつける。そして、使われていないものの中からランダムに一つ取得することを繰り返すというアルゴリズムだ。アルゴリズムとしては汚いけれども、基本的にはこれによってきちんとランダムに取得することが出来る。これは以下のように示すことが出来る。
上記のrand関数によって初期化される$selectは最初は1からnの範囲の乱数であり、次は1からn-1の乱数・・・というようになっている。この$selectの値が取りうる場合の数は、n*(n-1)*(n-2)*....(n-m+1)であり、それら(=乱数の組)は全て等確率で生成される(でなければ、randが擬似乱数としての仕様を満たしていない)。で、その生成された「乱数の組」の一つが、一つの順列と一対一に対応している。
具体例としてn=5, m=3の場合を考える。「乱数の組」が(5,4,3)であれば順列(5,4,3)を生成するし、「乱数の組」が(1,1,1)であれば(1,2,3)を生成するし、乱数の組が(1,2,3)であれば(1,3,5)を生成する。
したがって、このアルゴリズムによってランダムな順列が生成されると言うことが示せた。で、順列がランダムならば組み合わせがランダムかといえば、これも簡単に示せる。m個の組み合わせが生成する順列の可能性は、m!であることが自明である。従って各ランダムな組み合わせは、排他的にm!個のランダムな順列と対応付けされる。以上の理由によって、ランダムな組み合わせを生成することが出来たと言える。

さて、次にO(n*log(n))のアルゴリズムを紹介しよう。これ以下では、それがランダムかどうかについての議論は行わない。というのは、すぐ上の証明とほぼ同じ方法だからだ。

my @array = map {[$_, rand()]} (1..$n);
@array = sort {$a->[1] <=> $b->[1]} @array;
foreach(0..$m-1){
	print $array[$_]->[0], "\n";
}

このアルゴリズムは、1からnまでの各整数にランダムな数を割り当てて、そのランダムな数でsortを行うと言うアルゴリズムだ。見易さのためにmapとsortを別の行にしてみたが、当然1行で書き、さらに@arrayに多重配列のデータ構造を残さないことも出来る。

my @array = map {$_->[0]} 
            sort {$a->[1] <=> $b->[1]}
            map {[$_, rand()]} (1..$n);

ここからm個のスライスを取ってしまえばいいわけだ。これがO(n*log(n))であるのは自明だろう。もちろん、言語のsort関数の仕様しだいだが。

最後にO(n)のアルゴリズムを書いてみよう。

my @array = (1..$n);
for(0..$n-1){
	my $target = rand($n - $_);
	my $tmp = $array[$target];
	$array[$target] = $array[$n - $_];
	$array[$n - $_] = $tmp;
}

一番最後の要素を、全ての要素の中からランダムに選んだものとswapを行う。次に一番最後の要素以外のものを同様にswapしていく。このアルゴリズムは、ちょっと間違いやすい部分がある。というのは、一番最後の要素を一番最後の要素以外のものとswapするアルゴリズムと間違いやすい。これを行ってしまうとランダムにならないので注意。これについての詳しい説明は省略。
さて、結論としてお薦めなのはどれかだけれども、もしもCやJavaであれば一番最後のものをお薦めしたい。速いし書きやすい。だけれども、Perlならば二番目のものが書きやすいし、間違いにくいので良いのではないかと思う。そんなに大きなnでなければ、n*log(n)とnはほぼ同じ効率だったりするし。

追記：Pla君に、2番目の手法はリストに対しては特に有効かもと言う指摘を受けた。3番目の手法は、おそらくリストに対して普通に使うとO(n^2)になる上に、関数型言語ならば2番目は書きやすいというのが理由。リストに対してO(n)のアルゴリズムもあるかもしれないけれども。