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