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

Re: [問題] 不重覆的排列組合

看板Prob_Solve (計算數學 Problem Solving)作者yauhh (喲)時間12年前 (2012/06/07 22:10)推噓0(0推 0噓 6→)

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

※ 引述《dlikeayu (太陽拳vs野球拳)》之銘言： : 有個問題想要請較大家 : 我有兩組SET : 甲 {A,B,C}優先權低 : 乙{A,D,E}優先權高 : 然後我有一串值 : {B,C,E,B,A,D,E} : 我要從中選出來 : 甲或乙各有幾組 : 被選走的就不能再被用 : 所以要是乙跟甲都能組合的話 : 乙會優先抽走我會這樣子想: 像Erlang這個語言有一個運算子是簡單的差集運算,像 [b,c,d,e,b,c] -- [a,b,c] 會得到 [d,e,b,c], 對一個元素刪掉對應的元素只會刪一項. 這個運算是Erlang內建運算符號,內容最起碼會是循序搜尋,若找到符合的項目就刪除, 刪除之後換搜尋下一個指定元素. 基於這個運算方式,我先寫一個可能會擷取成功或者會擷取失敗的函數: -module(diff). -compile(export_all). extract(Xs, Ys) -> Zs = Ys -- Xs, if length(Zs) + length(Xs) == length(Ys) -> {ok, Zs}; true -> {failure, Ys} end. 刪成功,丟出刪成功的Xs; 無法完整刪去,丟出未刪除的原值Ys. 然後有個函數是 count_extract 是求從一列值中可以取出一組或零組指定的集合: count_extract(Xs, Ys) -> R = extract(Xs, Ys), case R of {ok, Zs} -> {1, Zs}; {failure, Zs} -> {0, Zs} end. 假如能取走整個集合的內容,就丟出 1 和其餘值; 假如不能,會丟出 0 和其餘值. 所以在執行環境中,以下二行執行命令就可以看出效果: > diff:count_extract([a,d,e],[b,c,e,b,a,d,e]). {1, [b,c,b,e]} > diff:count_extract([a,b,c],[b,c,b,e]). {0, [b,c,b,e]} 當然這個執行順序可以寫成函數比較簡單,假設輸入一列集合[[a,d,e],[a,b,c]], [a,d,e]集合排在前面代表優先順序高,那以下函數就可以用: instances([], Ys) -> {[], Ys}; instances([Xs|Xss], Ys) -> {N, Zs} = count_extract(Xs, Ys), {Ns, Zs1} = instances(Xss, Zs), {[N|Ns], Zs1}. > diff:instances([[a,d,e],[a,b,c]], [b,c,e,b,a,d,e]). {[1,0],[b,c,b,e]} 然後可以有個外層的模組,決定要按照什麼優先權把集合一組一組抽出來. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 59.112.225.213