将列表拆分成2个等于erlang的列表

Question

我想知道如何将给定列表拆分为两个列表，以使两个列表具有相同的总和。我想通过使用并发来做到这一点。我在erlang做这个。

所以，我正在做这样的事情： 阅读列表，如果它的总和是偶数，那么继续否则失败。获取列表的第一个元素，并检查它是否大于总和的一半，如果不是，则将该元素添加到新列表中。接下来，我将列表的第二个元素，检查这个元素和新列表的总和，并执行相同的操作。等等。这样，当新列表中的总和等于第一个列表总和的一半时，它会调用另一个函数发送其余元素。

-module(piles_hw). 
-compile(export_all). 

start([]) -> 0; 

start(List) -> 
Total = lists:foldl(fun(X, Sum)-> X+Sum end,0,List), 

if (Total rem 2) == 0 -> 
    Total/2, 
    copy_to_list_one([],List,start(List)); 
    true -> 
    func_fail() 
end. 

copy_to_list_one(L1,[H|T],X)-> 
    Y =lists:sum(L1)+H, 
    if Y<X -> 
     copy_to_list_one(lists:append(L1,[H]),lists:delete(H,[H|T]),X); 
     Y==X -> 
     take(lists:append(L1,[H])); 
     Y>X -> 
     copy_to_list_one(L1,lists:delete(H,[H|T]),X) 
end; 
copy_to_list_one(L1,[],X)-> 
    copy_func_two([1,2,3,4,19,20,28,14,11],X). 
copy_func_two([H|T],X)-> 
    copy_to_list_one([],lists:append(T,[H]),X). 

    take(L3)->  
    io:format("~w",[L3]). 

func_fail() -> 
    io:format("~n fail ~n"). 

但是，这样我有时会进入一个无限循环。有人可以帮忙吗？

Answer 1

编辑：

帕斯卡是完全正确的：没有任何算法（至少不是我能想出），可以通过同时运行在列表中向下一个项目解决某些集。 （特别是当列表总和的一半等于X * N，其中X在列表中出现N次时）。我最初在这里提出了一个有缺陷的算法。

这让我兴奋的方式，因此这里是一个详尽的算法，涉及[{P, (List - P)} || P <- powerset(List)]对。

有一些lists:usort/1 shenanig在那里，我没有清理，以最后比较之前uniquested列表（否则你会得到重复类似的对，这是丑陋的）。总之，丑陋的，但现在正确的：

comblit(List) -> 
    Power = powerset(List), 
    Lists = lists:usort([lists:sort([Z, lists:subtract(List, Z)]) || Z <- Power]), 
    Pairs = lists:map(fun([H|[B|[]]]) -> {H, B} end, Lists), 
    [{Z, X} || {Z, X} <- Pairs, lists:sum(Z) == lists:sum(X)]. 

powerset([H|T]) -> 
    Part = powerset(T), 
    powerset(Part, H, Part); 
powerset([]) -> [[]]. 

powerset(A, Part, [H|T]) -> 
    powerset([[Part|H]|A], Part, T); 
powerset(A, _, []) -> A. 

这仍然不是一个并发的解决方案，但现在的路径，使得它同时是很多更加明显。

感谢您指出，帕斯卡尔。那很有趣。

Answer 2

我有这样的解决方案，是不是并发：

-module(split). 

-export([split/1,t_ok/0,t_too_long/0,t_fail/0,t_crash/0]). 
%% [EDIT] 
%% Don't use this code, it fails with negative integers! 


% Exported 

%% take a list and split it in 2 list which sum are equals 
split(L=[_|_]) -> 
    T2 = lists:sum(L), 
    {ok, TRef} = timer:send_after(20000,too_long), 
    R = case T2 rem 2 of 
     1 -> {error,fail}; 
     0 -> split(tl(L),[hd(L)],[],T2 div 2,hd(L),0) 
    end, 
    timer:cancel(TRef), 
    R. 

% test 

t_ok() -> split([1,2,3,4,5,6,7]). 

t_too_long() -> split(lists:seq(1,3+4*100000)). 

t_fail() -> split([2,4,6,10000,8,6]). 

t_crash() -> split([]). 

% private 

split([H|Q],A,B,T,Asf,_Bsf) when H + Asf == T -> {ok,{[H|A],B ++ Q}};       
split([H|Q],A,B,T,_Asf,Bsf) when H + Bsf == T -> {ok,{A ++ Q,[H|B]}};       
split([H|Q],A,B,T,Asf,Bsf) when H + Asf > T, H + Bsf < T -> c_split(Q,A,[H|B],T,Asf,Bsf+H);  
split([H|Q],A,B,T,Asf,Bsf) when H + Asf < T, H + Bsf > T -> c_split(Q,[H|A],B,T,Asf+H,Bsf);  
split([H|Q],A,B,T,Asf,Bsf) when H + Asf < T, H + Bsf < T -> 
    case c_split(Q,A,[H|B],T,Asf,Bsf+H) of 
     {error,fail} -> c_split(Q,[H|A],B,T,Asf+H,Bsf);             
     R -> R                    
    end; 
split([],A,B,_T,_T,_T)-> {ok,{A,B}};                     
split(_,_,_,_,_,_) -> {error,fail}. 

c_split(L,A,B,T,Asf,Bsf) -> 
    receive 
     too_long -> {error,too_long} 
    after 0 -> 
     split(L,A,B,T,Asf,Bsf) 
    end. 

要打开它的并发，可以通过到spawn_link几个进程的函数的调用替换线0 -> split(tl(L),[hd(L)],[],T2 div 2,hd(L),0)（尽可能有核心可用）用不同的初始条件启动split/6功能。 split/6必须有第7个参数：主进程的Pid将返回其答案。主进程等待答案，并停止

• 如果找到一个解
• 如果所有进程无法找到一个
• 如果出现超时

我已编辑的代码在@Odobenus注释之后（但它仍然在[] - > {ok，[]，[]}：o）上失败，并且我也创建了一个并发版本。有趣的是，对于这种问题以及我使用的输入列表（列表：seq），有很多解决方案，我选择的任何启动顺序都可以提供解决方案，因此并发版本较慢。