將列表拆分成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），有很多解決方案，我選擇的任何啓動順序都可以提供解決方案，因此併發版本較慢。