19221


EDIT:
最初に投稿した時は、N個の整数の合計の一般解を求める問題だと思っていたのですが、一般解だとNP完全問題になってしまうので、出題者の意図は３つ限定だったのだろうと思います。ですので３つの合計に改題しました。回答を考えてくださった皆さんすみません！

* * *

ある任意の長さのリストに符号つきの整数が格納されています。値の重複を許します。そこから３つの整数を取り出すとき、合計が0になる組み合わせを求めなさいという問題が解けません。どうぞご教授ください。

**条件**

  * itertoolsを使えば下のように簡単に計算できますが、itertoolsは使わないものとします。
  * メモリを3回走査するとtime complexity(CPUタイム)はO(N^3)になります。それよりは効率のよい方法で実装したいです。
  * space complexity(メモリ効率)は犠牲にしていいです。
  * ソートやリストのコピーなど前処理を行っても構いません。

**検算用のコード**

[code]

    import itertools
    l=[-3, 2, 1, -2, 0, 5, -1 , -1]
    for c  in itertools.combinations(l, 3):
        if sum(c) == 0:
            print c
    
[/code]

**答え**

[code]

    (-3, 2, 1)
    (-3, -2, 5)
    (2, -2, 0)
    (2, -1, -1)
    (1, 0, -1)
    (1, 0, -1)
    
[/code]

**今まで調べたこと**

itertools.combinationのマニュアルには同等のアルゴリズムのソースがありました。このアルゴリズムはO(N)だそうです。

[code]

    def combinations(iterable, r):
        # combinations('ABCD', 2) --> AB AC AD BC BD CD
        # combinations(range(4), 3) --> 012 013 023 123
        pool = tuple(iterable)
        n = len(pool)
        if r > n:
            return
        indices = range(r)
        yield tuple(pool[i] for i in indices)
        while True:
            for i in reversed(range(r)):
                if indices[i] != i + n - r:
                    break
            else:
                return
            indices[i] += 1
            for j in range(i+1, r):
                indices[j] = indices[j-1] + 1
            yield tuple(pool[i] for i in indices)
    
[/code]

これだけでも十分速いと思いますが、与えられた問題とデータの性質に合わせてより効率的な方法はないかと模索しています。

条件のところに書いていますが、ヒントはソートしても良いし、リストのコピーを作っても良い、とのことです。また取り出す個数が3でなくて2ならどうか？とも聞かれました。2つなら辞書にd[-1]=1などとして、リストに存在する符号が反対の値の組合せを保存しておけば、O(1)で計算できることになります。しかしこれでは重複する値に対応できないし、3つ以上に拡張できるのか、全く見当もつきません。

**類題**

部分和問題という類題は任意の数の部分和を探すもので、僕に与えられた問題はサブセットということになりそうです。なんとなく、見た目より遥かに難しい問題だということはわかりました。

[部分和問題](https://en.wikipedia.org/wiki/Subset_sum_problem)。NP完全だそうです...。

**さらに調べてわかったこと**

取り出す個数が３の時は"3sum問題"として、ダイナミックプログラミング(DP、動的計画法)のO(N^2)の解が知られている。

[本家StackOverflow N=3の時の回答](https://stackoverflow.com/questions/22905617/given-
an-array-of-sorted-integers-how-can-i-find-if-there-exists-a-set-of-3-ele)
コードも簡単。  
[３和問題](https://en.wikipedia.org/wiki/3SUM)


CC BY-SA 3.0
2015-11-20T16:17:58.913
19098
2017-08-06T01:42:49.663
2017-08-06T01:42:49.663
19110
7837
question
python アルゴリズム
リストから取り出した3つの整数の合計が0になる組み合わせ


ほとんど本家からのコピーですが、3つの和限定の解です。

[code]

    l=[-3, 2, 1, -2, 0, 5, -1 , -1]
    l.sort()
    M = len(l) - 1
    for i, e in enumerate(l):
        j = i + 1
        k = M
        while k > j:
            s = l[i] + l[j] + l[k]
            if s == 0:
                print l[i], l[j], l[k]
                k -= 1
            elif s > 0:
                k -= 1
            else:
                j += 1
    
[/code]

**結果**

[code]

    -3 -2 5
    -3 1 2
    -2 0 2
    -1 -1 2
    -1 0 1
    -1 0 1
    
[/code]


CC BY-SA 3.0
2015-11-23T18:08:05.580
19221
2015-11-23T18:36:26.490
2015-11-23T18:36:26.490
7837
7837
19098
answer


とりあえず、`itertools.combination`はO(N)ではありません。O(N^3)です。  
というのも、`combination(iterable, 3)`は、`iterable`から3個の要素を選ぶすべての場合を返すので、  
N個から3個選ぶ方法、N(N-1)(N-2)/6だけ時間がかかります。

長さ`N`の配列`a`に対して、O(N^2)解法は以下の通りです。

  1. 連想配列`dict`を用意し、`dict[i]=(a[j]=iとなるjの個数)`となるようにする
  2. `dict`のキーを配列`x`にソートして格納する
  3. `sum=0`とする
  4. `0<=i<j<len(x)`に対して、5.を実行する。
  5. `-(x[i]+x[j])`が`dict`のキーとして含まれていれば、`sum+=dict[-(x[i]+x[j])]`とする
  6. `sum`が答え


CC BY-SA 3.0
2015-12-25T07:19:40.333
20356
2015-12-25T07:19:40.333
13805
19098
answer