作者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