作者yauhh (喲)
看板Prob_Solve
標題Re: [問題] 不重覆的排列組合
時間Thu Jun 7 22:10:03 2012
※ 引述《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
1F：→ dlikeayu:我跪了.. 06/07 23:20
2F：→ yauhh:別,別,別,這個東西很普通啊 06/08 00:11
3F：→ u941716:可以先讓乙抽完，然後再把剩下的給甲嗎？ 06/10 22:50
4F：→ u941716:也就是乙可以拿min(N(A),N(D),N(E))組 06/10 22:52
5F：→ yauhh:樓上什麼意思呢,看不懂 06/12 22:02
6F：→ u941716:我沒考慮順序，抱歉了！請不要理我 06/13 01:12