ランダム順列

id:succeed:20060127#1138378979
2番目のやつは間違ってるような。
ソートアルゴリズムが安定だと小さい数が先に出てくる確率が高いし、
そうでなくてもランダムではない。
例えば n=2 で、ソートアルゴリズムが安定で、
rand() の返り値が k 通りあるとすると
(k+1)/(2k) の確率で先に 1 が出る。
普通は k が大きすぎて分からないけど

my $n = 2;
my $m = 1;

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

とかにして100回ほど実験すると 3/4 くらいの割合で 1 が出る。

関数型っぽく実装するなら木構造を使うのが無難かと。
以下 ocaml

module M = Map.Make
(struct
   type t = int
   let compare x y = x - y
 end)

let find x env = try M.find x env with Not_found -> x
let rec iter n env acc =
  if n <= 0 then acc
  else let r = Random.int n + 1 in
  iter (n-1) (M.add r (find n env) env) (find r env :: acc)

let random_list n =
  iter n M.empty []

アルゴリズムは3番目とほぼ同じで時間はO(n*log n)。