作者yauhh (喲)
看板Prob_Solve
標題Re: [請益] 列出所有進出的排列組合
時間Wed Aug 11 21:42:41 2010
※ 引述《aerolien (aerolien)》之銘言：
: A_in、A_out、B_in、B_out、C_in、C_out、D_in、D_out
: 這幾種狀況去作排列組合
: 限制為
: A_in 先於 B_in 先於 C_in 先於 D_in
: 要先 in 才能 out
: 而out則沒限制先後
: 若單純只用數學去算是105種情況
: 只是現在必須要探討這105種情況必須一一列出
: 想用程式寫
: 該怎麼去解 ? 只有用窮舉一途嗎？
數學是吧? 可以用Prolog寫:
首先定義項目前後關係, check(A, Bs) 是檢查一列資料以A開頭,並以Bs為後續序列:
check('A_in', Zs) :-
member('B_in', Zs),
member('C_in', Zs),
member('D_in', Zs),
member('A_out', Zs).
check('B_in', Zs) :-
not(member('A_in', Zs)),
member('C_in', Zs),
member('D_in', Zs),
member('B_out', Zs).
check('C_in', Zs) :-
not(member('A_in', Zs)),
not(member('B_in', Zs)),
member('D_in', Zs),
member('C_out', Zs).
check('D_in', Zs) :-
not(member('A_in', Zs)),
not(member('B_in', Zs)),
not(member('D_in', Zs)),
member('D_out', Zs).
check(X, _) :-
not(member(X, ['A_in','B_in','C_in','D_in'])).
然後,按照以下這個"排列"的邏輯規則: (按:請注意這題是排列,不是組合.)
permu([], []).
permu(Xs, [Y|Zs]) :-
member(Y, Xs),
without(Xs, [Y], Xs1),
permu(Xs1, Zs).
可能改寫一下,變成一種附帶前後條件的排列:
io(['A_in','A_out','B_in','B_out','C_in','C_out','D_in','D_out']).
permu_io([], []).
permu_io(Xs, [Y|Zs]) :-
member(Y, Xs),
without(Xs, [Y], Xs1),
permu_io(Xs1, Zs),
check(Y, Zs).
without(As, [B], Cs)的意思是從As這種資料序列拿走其中存在的B項目,得到結果
為Cs序列:
without([], [_], []).
without([Y|Ys], [Y], Ys).
without([X|Ys], [Y], [X|Zs]) :- X \= Y,
without(Ys, [Y], Zs).
最後,取解的主要程式是:
solution(Answer) :-
io(List),
permu_io(List, Answer).
而以下一行查詢,可以找出共有多少種排列:
?- setof(Xs, solution(Xs), SoXs), length(SoXs, N).
SoXs = ...
N = 105.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.108.129
1F：→ yauhh:Prolog的演算法,可以算是DFS,backtracking. 08/11 21:43
2F：推 aerolien:感謝解答 08/12 03:12