二郎算法返回其中当彼此相加等于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，（而不是依赖于数据顺序）。