二郎算法返回其中當彼此相加等於X

Question

給定一個列表整數的對列表，例如

[1, 45, 1, 99, 3, 5, 95, 1, 5, 97, 3, 99, 87] 

返回從該列表，加起來爲100作爲項目的對被消耗，不應該重新評估。在上面的情況下，輸出將是：

[{1,99}, {1, 99}, {3,97}, {5,95}] 

該列表並不假定爲排序，如在示例中重複對應該起作用。

方法的優點/缺點會很好理解（BigO的複雜性，空間/時間）。

Answer 1

在外殼，因爲它使用遞歸的匿名功能，它僅適用於R17，但是這將是確定與早期的Erlang版本的模塊

1> L = [1, 45, 1, 99, 3, 5, 95, 1, 5, 97, 3, 99, 87]. 
2> F= fun F([],R) -> R; 
2>  F([H|T],R) -> Rest = lists:dropwhile(fun(X) -> X+H /= 100 end,T),     
2>      case Rest of 
2>       [] -> F(T,R); 
2>       [Found|_] -> F(lists:delete(Found,T),[{H,Found}|R]) 
2>      end 
2> end. 
#Fun<erl_eval.36.90072148> 
3> F(L,[]).                         
[{5,95},{3,97},{1,99},{1,99}] 
4> 

它再現究竟在什麼如果我有，我會做做自己：

• 將這個列表的第一個元素，
• 看看列表中的其餘一對，
  • 如果沒有配對使用列表的其餘部分重新啓動該過程，如果找到一對，請記錄該配對，從列表的其餘部分中刪除找到的元素，並使用剩餘列表重新啓動。
• 繼續，直到列表爲空。

這第一個實現是在使其工作精神，我已經做了快一個，第一個排序列表。下面的模塊實現了兩種解決方案以及一些功能來測試和評估性能（在兩種極端情況下，對於長列表，新解決方案要快得多：沒有解決方案或每個術語都屬於一對）。在我的PC上，s2的速度比s1快2500多倍，隨機列表爲100000個元素。

-module (sum). 

-compile([export_all]). 

s1(L,S) -> s1(L,S,[]). 

s1([],_S,R) -> R; 
s1([H|T],S,R) -> 
    Rest = lists:dropwhile(fun(X) -> X+H /= S end,T),     
    case Rest of 
     [] -> s1(T,S,R); 
     [Found|_] -> s1(lists:delete(Found,T),S,[{H,Found}|R]) 
    end. 

s2(L,S) -> 
    Linc = lists:sort(L), 
    Ldec = lists:reverse(Linc), 
    s2(Linc,Ldec,S,[]). 

s2(Linc,Ldec,_S,R) when Linc == [] ; Ldec == [] ; hd(Linc) > hd(Ldec) -> R; 
s2([H,H|Linc],[H,H|Ldec],S,R) when S == 2*H -> s2(Linc,Ldec,S,[{H,H}|R]); 
s2([H1|Linc],[H2|Ldec],S,R) when S == H1+H2, H1/=H2 -> s2(Linc,Ldec,S,[{H1,H2}|R]); 
s2([H|Linc],Ldec,S,R) when H + hd(Ldec) < S -> s2(Linc,Ldec,S,R); 
s2(Linc,[_H|Ldec],S,R) -> s2(Linc,Ldec,S,R). 


%% Test and performance 

compare(S1,S2) -> 
    S = normalize(S1), 
    S = normalize(S2). 


normalize(S) -> lists:sort([{min(X,Y),max(X,Y)} || {X,Y} <- S]). 

shuffle(P) when is_list(P) -> 
    Max = length(P)*10000, 
    {_,R}= lists:unzip(lists:keysort(1,[{random:uniform(Max),X} || X <- P])), 
    R. 

test1(S) -> % every term is part of a solution pair 
    random:seed(erlang:now()), 
    L = shuffle(lists:seq(1,S)), 
    test(L,S+1). 

test2(S) -> % no solution 
    random:seed(erlang:now()), 
    L = shuffle(lists:seq(1,S)), 
    test(L,2*S). 

test3(S) -> % random 
    random:seed(erlang:now()), 
    L = [random:uniform(2*S) || _ <- lists:seq(1,S)], 
    test(L,S). 

test(L,S) -> 
    {T1,S1} = timer:tc(sum,s1,[L,S]), 
    {T2,S2} = timer:tc(sum,s2,[L,S]), 
    compare(S1,S2), 
    {T1,T2,S1}. 

Answer 2

我不那麼流利的算法和他們的表現，但這裏是我所知道的。我的總體思路是，以列表分成兩個子列表的元素> = 50和< 50.至少這可以確保你不必去尋找對每個列表，但只有他們之間：

-module(test). 
-export([add_to_100/1]). 

add_to_100([]) -> []; 
add_to_100(List) -> 
    {L1, L2} = split(List, [], []), 
    find_match(L1, L2). 

%% Do matching between 2 lists 
find_match([], _) -> []; 
find_match(_, []) -> []; 
find_match([H1|T1], L2) -> 
    case match_element(H1, L2, []) of 
     {{A, B}, Left} -> [{A, B} | find_match(T1, Left)]; 
     {{}, Left} -> find_match(T1, Left) 
    end. 

%% Match every element with list of integers. 
%% Return match pair and exclude matched element from list of integers. 
match_element(_, [], Rest) -> {{}, Rest}; 
match_element(E, [H|T], Rest) when E + H == 100 -> {{E,H}, Rest ++ T}; 
match_element(E, [H|T], Rest) -> match_element(E, T, [H|Rest]). 

%% Split input list into two sublists - L1 < 50 and L2 >= 50 
split([], L1, L2) -> {L1, L2}; 
split([H|T], L1, L2) when H < 50 -> split(T, [H|L1], L2); 
split([H|T], L1, L2) -> split(T, L1, [H|L2]). 

例如：

85> c(test). 
{ok,test} 
86> test:add_to_100([1, 45, 1, 99, 3, 5, 95, 1, 5, 97, 3, 99, 87]). 
[{3,97},{5,95},{1,99},{1,99}] 
87> test:add_to_100([1, 45, 1, 99, 3, 5, 95, 1, 5, 97, -50, 3, 99, 87, 100, 0, 150]). 
[{0,100},{3,97},{-50,150},{5,95},{1,99},{1,99}] 

執行它後，我已經意識到，它不處理對{50，50} - 反正你可以把它作爲一個特殊的情況下，這個算法。儘管這個解決方案並不完整，但應該讓您深入瞭解Er​​lang中的模式匹配，尾遞歸和列表操作，在解決此問題時您肯定需要這些操作。

Answer 3

你可以使用列表理解與警衛來做到這一點。

find_pairs(List) -> 
    [{X, Y} || X <- List, 
      Y <- List, 
      X+Y =:= 100]. 

這種做法有當然n^2複雜性，但這樣做幾乎任何其他。最後，你必須採取每個元素（即n），並相互驗證（這是* n）。你可以引入一些優化，就像在another answer中建議的那樣，但仍然很大O會留n^2。所以我認爲沒有意義。

如果這樣的複雜性會導致我一些問題，事實上我將不得不優化，我會盡量減少這第二個*n。由於這第二部分只是價值查詢（對於eny X，您正在尋找其餘值的100 -X）。你可以試着去看看gb_tree。創建這樣的樹需要一些n log n，但這隻能完成一次。所有查找將帶你log n。所以最後這種方法會有複雜性。

在其他語言中，而不是使用gb_tree，只需對列表進行排序，然後執行二進制搜索以進行值查找（同樣，位O爲n log n）。但是我們必須記住，在Erlang列表中不是數組。它們是「鏈接列表」，查找列表中的一個值並不是恆定的，但可能具有複雜性。而這個n對我們的算法有影響，可能會給我們n * n long n，這比最初的n^2差。

---

編輯後，我的算法沒有經過一些要求@Steve Vionski評論。使用我的方法，在配對來自[1, 99, 99]的值而不是[{1, 99}]時，我會返回[{1,99},{1,99},{99,1},{99,1}]。

我真的需要閱讀更仔細的問題。謝謝史蒂夫指出這一點。儘管如此，我仍然想保留我的初始答案，因爲它清楚地顯示了算法的複雜性，這是我在答案中所關注的內容。

不過我想對於任何可能的混亂表示歉意，並提供工作液：

find_pairs(List) -> 
    find_pairs(List, _Pairs = [], _Sum = 100). 

find_pairs([], Pairs, _Sum) -> 
    Pairs; 
find_pairs([First | Tail], Pairs, Sum) -> 
    case pop(Tail, Sum - First) of 
    {Second, Rest} -> 
     find_pairs(Rest, 
       [{First, Second} | Pairs], 
       Sum); 
    not_found -> 
     find_pairs(Tail, 
       Pairs, 
       Sum) 
    end. 


pop(List, Value) -> 
    pop(List, Value, []). 

pop([], _Value, _Processed) -> 
    not_found; 
pop([Value | Tail], Value, Processed) -> 
    {Value, Processed ++ Tail}; 
pop([Different | Tail], Value, Processed) -> 
    pop(Tail, Value, [Different|Processed]). 

並再次對這個算法的複雜性。 find_pairs剛剛進入低谷列表，所以pop，所以它似乎是n^2。事實證明，這並非如此簡單。還有其他功能++，這再次由於鏈表性質可能具有n的複雜性。所以最後，根據輸入，我們可以體驗n*(2*n)。仍然在BigO中，它是n^2，但值得注意的是，在算法中加入更多工作（或代碼行）並不能保證提高性能。

而且也有一個簡單的解決方案。 ++有左元素的複雜性。因此，連接pop內的兩個列表，而不是將Processed添加到Tail，可以將Tail添加到Processed。這樣，當我們在k的位置（和調用k後）找到我們的Value時，我們在連接期間只需要做n - k個附加工作。這保證pop將會比n做更多的工作。我們回到整個算法的直接n^2，（而不是依賴於數據順序）。