DouKaku?beta

Comment detail

n人中m人が当選するくじ (Nested Flatten) 
SWI-Prologです。

長さnのリストからm個をランダムに選びます。
リストの最初の要素をm/nの確立で選び、
    選ばれた       ⇒ 残りの長さn-1のリストからm-1個を選ぶ
    選ばれなかった ⇒ 残りの長さn-1のリストからm個を選ぶ
という再帰的なアルゴリズムです。
結局は普通のランダム・サンプリングと同じです。

これだとリストでも計算量が線形時間になります。

実行例（n=100, m=5の場合）：
:- numlist(1, 100, L), sample(L, 5, Samples).
L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
Samples = [1, 6, 36, 68, 85] 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
%%	sample(+List1, +N, -List2)
%
%	List2はList1からランダムにN個の要素を選んだもの

sample(Xs, N, Ys) :-
	length(Xs, Len),
	N1 is max(0, min(N, Len)),
	sample_aux(Xs, Len, N1, Ys).

sample_aux(_, _, 0, []) :- !.
sample_aux([X|Xs], Len, N, [X|Ys]) :-
	random(Len) < N, !,
	Len0 is Len - 1,
	N0 is N - 1,
	sample_aux(Xs, Len0, N0, Ys).
sample_aux([_|Xs], Len, N, Ys) :-
	Len0 is Len - 1,
	sample_aux(Xs, Len0, N, Ys).

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]