PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [請益] 列出所有進出的排列組合

看板Prob_Solve (計算數學 Problem Solving)作者yauhh (喲)時間14年前 (2010/08/11 21:42)推噓1(1推 0噓 1→)

留言2則, 2人參與討論串3/3 (看更多)

※ 引述《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