Search for sets of vectors summing to zero

Question

I have four arrays (set1, set2, ...) of 3 arrays. For example.

set1 = [array([1, 0, 0]), array([-1, 0, 0]), array([0, 1, 0]), ...]

I need to find how many combinations of vectors stack with zero. A simple way to solve this problem:

for b1 in set1:
  for b2 in set2:
    for b3 in set3:
      for b4 in set4:
        if all(b1 + b2 + b3 + b4 == 0):
          count = count + 1

However, it goes like O (n ^ 4), and based on the 3sum algorithm, I guess I can do O (n ^ 3), and speed is very important. Any conclusions on how to do this quickly in python?

Answer 1

Assuming that the inputs are lists of 1D arrays, as indicated in the sample data presented in the question, it seems you can use broadcastingafter stacking the strings in the input lists, for example:

import numpy as np

s1 = np.row_stack((set1))
s2 = np.row_stack((set2))
s3 = np.row_stack((set3))
s4 = np.row_stack((set4))

sums = s4[None,None,None,:,:] + s3[None,None,:,None,:] + s2[None,:,None,None,:] + s1[:,None,None,None,:]
count = (sums.reshape(-1,s1.shape[1])==0).all(1).sum()

-

In [319]: set1 = [np.array([1, 0, 0]), np.array([-1, 0, 0]), np.array([0, 1, 0])]
     ...: set2 = [np.array([-1, 0, 0]), np.array([-1, 1, 0])]
     ...: set3 = [np.array([1, 0, 0]), np.array([-1, 0, 0]), np.array([0, 1, 0])]
     ...: set4 = [np.array([1, 0, 0]), np.array([-1, 0, 0]), np.array([0, 1, 0]), np.array([0, 1, 0])]
     ...: 

In [320]: count = 0
     ...: for b1 in set1:
     ...:   for b2 in set2:
     ...:     for b3 in set3:
     ...:       for b4 in set4:
     ...:         if all(b1 + b2 + b3 + b4 == 0):
     ...:           count = count + 1
     ...:           

In [321]: count
Out[321]: 3

In [322]: s1 = np.row_stack((set1))
     ...: s2 = np.row_stack((set2))
     ...: s3 = np.row_stack((set3))
     ...: s4 = np.row_stack((set4))
     ...: 
     ...: sums = s4[None,None,None,:,:] + s3[None,None,:,None,:] + s2[None,:,None,None,:] + s1[:,None,None,None,:]
     ...: count2 = (sums.reshape(-1,s1.shape[1])==0).all(1).sum()
     ...: 

In [323]: count2
Out[323]: 3

Answer 2

, , , , Python C-, , , Cython: http://cython.org/. , . C , Python .

, (O [n ^ 2 log N]): https://cs.stackexchange.com/questions/2973/generalised-3sum-k-sum-problem. , , Python Cython .

EDIT:

, :

sum2 = np.add.outer(A,B)
sum3 = np.add.outer(sum2,C)
sum4 = np.add.outer(sum3,D)

sum4 [i, j, k, l] A [i] + B [j] + C [k] + D [1].

len(sum4) - np.count_nonzero(sum4)

Answer 3

numpy meshgrid:

http://docs.scipy.org/doc/numpy/reference/generated/numpy.meshgrid.html

1-D, .

set1 = set1.flatten() // etc

meshgrid(). 4 4- , . :

a,b,c,d = np.meshgrid(set1, set2, set3, set4)
total = a+b+c+d 

, 0 :

count = len(total) - np.count_nonzero(sum)

Answer 4

?

from numpy import array
def createset(min, max):
    xr = lambda: xrange(min, max)
    return [ array([x, y, z]) for x in xr() for y in xr() for z in xr() ]

set1 = createset(-3, 3)
set2 = createset(-2, 1)
set3 = createset(-4, 5)
set4 = createset(0, 2)

lookup = {}
for x in set1:
    for y in set2:
        key = tuple(x + y)
        if key not in lookup:
            lookup[key] = 0
        lookup[key] += 1

count = 0
for x in set3:
    for y in set4:
        key = tuple(-1 * (x + y))
        if key in lookup:
            count += lookup[key]

print count

, . , , 0.

Answer 5

itertools.product sum:

from itertools import combinations
sum(1 for i in produt(set1,set2,set3,set4) if sum(i)==0)

It will be faster than your code, but still O (n ⁴ ) for greater speed you can get the product using Numpy from itertools.