0

両方のリストの合計が同じになるように、特定のリストを 2 つのリストに分割する方法を知りたいです。並行性を使用してそれを行いたいです。私はこれをアーランでやっています。

だから、私はこのようなことをやっています: リストを読んで、その合計が偶数なら続行し、そうでなければ失敗します。リストの最初の要素を取り、それが合計の半分より大きいかどうかを確認し、そうでない場合は、この要素を新しいリストに追加します。次に、リストの 2 番目の要素を取得し、この要素と新しいリストの要素の合計を確認して、同じ操作を行います。などなど..新しいリストの合計が最初のリストの合計の半分に等しい場合、別の関数を呼び出して残りの要素を送信します。

-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").

しかし、このように無限ループに陥ることがあります。誰か助けてくれませんか？

4

2 に答える 2

0

編集：

Pascal は完全に正しかったです。一度に 1 項目ずつリストを実行して特定のセットを解決できるアルゴリズムはありません (少なくとも私が思いつくことはできませんでした)。(特に、リストの合計の半分が X * N に等しく、X がリストに N 回存在する場合。) 最初に、ここに欠陥のあるアルゴリズムを入れました。

それは私を最もオタクな方法で興奮させたので、ここに のペアを含む網羅的なアルゴリズムがあり[{P, (List - P)} || P <- powerset(List)]ます.

lists:usort/1最終的な比較の前にリストを一意化するためにクリーンアップしなかったいくつかの悪ふざけがあります (そうしないと、似たようなペアが重複してしまい、見苦しくなります)。とにかく、醜いが、今は正しい：

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.

これはまだ同時実行ソリューションではありませんが、同時実行への道はより明確になりました。

指摘してくれてありがとう、パスカル。それはちょっと楽しかったです。

于 2014-10-02T01:04:05.650 に答える
0

同時ではないこのソリューションがあります：

-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.

0 -> split(tl(L),[hd(L)],[],T2 div 2,hd(L),0)同時実行するには、異なる初期条件で split/6 関数を開始する複数のプロセス (利用可能なコアがある限り) を spawn_link する関数の呼び出しで行を置き換えることができます。split/6 には 7 番目のパラメータが必要です。それは、応答を送り返すメイン プロセスの Pid です。メインプロセスは応答を待って停止します

  • 解決策が見つかった場合
  • すべてのプロセスが 1 つを見つけられない場合
  • タイムアウトが発生した場合

@Odobenus の発言に続いてコードを編集しました (ただし、[] -> {ok,[],[]} :o ではまだ失敗します)。並行バージョンも作成しました。おもしろいことに、この種の問題では、私が使用する入力リスト (a lists:seq) を使用すると、非常に多くの解決策があり、選択した開始シーケンスで解決策が得られるため、並行バージョンは遅くなります。

于 2014-10-02T04:23:55.360 に答える