n人中m人が当選するくじ in Prolog DouKaku?

n人の中から公平にm人を選ぶ、くじ引きプログラムを作ってください。

基本的なリスト操作述語が無いので、長たらしくなります。
リスト生成→乱打舞頭→頭から順番にN個という流れです。
randomizeは、M人分だけすれば良い気もします。

serial(S,E,[]):-S > E.
serial(S,E,[S|R]):-succ(S,S1),serial(S1,E,R).

remove([L|Ls],1,L,Ls).
remove([],_,_,_):-fail.
remove([L|Ls],N,E,[L|R]):-succ(N1,N),remove(Ls,N1,E,R).

randomize([X],[X]).
randomize(L,R):-random(N),length(L,Ll),Nx is floor(N * Ll) + 1,remove(L,Nx,Le,Rs),randomize(Rs,Rss),R=[Le|Rss].

take(_,0,[]).
take([L|Ls],N,[L|R]):-succ(N1,N),take(Ls,N1,R).

lot(N,M,R):-serial(1,N,L0),randomize(L0,L1),take(L1,M,R).

:-lot(20,5,R),writeln(R),halt.

#1248は無かったことに。 Nまでの列生成→ランダムにM個取り出しです。

serial(S,E,[]):-S > E.
serial(S,E,[S|R]):-succ(S,S1),serial(S1,E,R).

remove([L|Ls],1,L,Ls).
remove([L|Ls],N,E,[L|R]):-succ(N1,N),remove(Ls,N1,E,R).

randomize(0,_,[]):-!.
randomize(I,L,R):-random(N),length(L,Ll),Nx is floor(N * Ll) + 1,remove(L,Nx,Le,Rs),succ(I1,I),
                  randomize(I1,Rs,Rss),R=[Le|Rss].

lot(N,M,R):-serial(1,N,L0),randomize(M,L0,R).

:-lot(20,5,R),writeln(R),halt.

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]

%%	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).

DouKaku?

n人中m人が当選するくじ

Posted feedbacks - Prolog

Index

Feed

Other

Link

Pathtraq