整数配列からa + b + c = 0を満たす様な組み合わせを求める

Three sum algorithm solution – StackOverflow

これも,numpyのブロードキャストを利用できる.

import numpy as np

c, cnt = np.unique(np.array([-4, -2, -2, -2, 0, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6]), return_counts=True)
b = c[:, np.newaxis]
a = c[:, np.newaxis, np.newaxis]

ind = np.arange(c.size)
d = {k: v for k, v in zip(ind, cnt)}

print('A solution set is: ')
for x in set(map(tuple, np.sort(np.argwhere(a+b+c == 0)))):
    if sum([d[i] - list(x).count(i) for i in x]) > 0:
        print(f'[{c[x[0]]}, {c[x[1]]}, {c[x[2]]}]')

A solution set is:
[-2, -2, 4]
[-4, 0, 4]
[-4, -2, 6]
[-4, 2, 2]
[-4, 1, 3]
[-2, 0, 2]

最も,この場合は単に組み合わせの問題とみてitertoolsを使う方がシンプルか.

from itertools import combinations

li = [-4, -2, -2, -2, 0, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6]

res = [elm for elm in combinations(li, 3) if sum(elm)==0]
list(map(list, set(map(tuple, res))))

[[-4, -2, 6], [-2, 0, 2], [-4, 1, 3], [-2, -2, 4], [-4, 2, 2], [-4, 0, 4]]

実行時間はitertools.combinationsは指数的に計算量が増大するのに対して,
numpyの方はだいたい対数時間なので,コードは(後半部分)汚いけど実効性はある.
 
 
 
関連:
配列要素の合計値がターゲット値になる様な組み合わせを全て求める

How can I list all of the ways to sum a list of numbers to N, with repeats, in python?

不定方程式を解く

リストからユニークな要素(⊇リスト)だけ残す

広告
カテゴリー: 未分類 パーマリンク

整数配列からa + b + c = 0を満たす様な組み合わせを求める への1件のフィードバック

  1. ピンバック: 制約最適化問題の実現可能な領域を視覚化したい | 粉末@それは風のように (日記)

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中