All possible sets of integers with sum of zero

Edit: OK, I overcame duplicate issue.

We can generate combinations with possible sums and weghts and put them into dictionary. Note that some pairs give some combinations, so value if dict is list of list.

Then for every weight1/sum pair we seek another pair with the same sum (to make zero) and weight2 should give weight1+weight2 in needed range.

dic = dict()
zeros = []

def makebag(mm, mm0, last, lst):
    if mm == 0:
        sm = sum(lst)
        if sm:
            ky = (mm0, sm)
            if ky in dic:
                dic[ky].append(lst)
            else:
                dic[ky] = [lst]
        return
    for i in range(last, mm - 1):
        makebag(mm - i - 2, mm0, i, lst + [i])

def makezero(m):
    for i in range((m + 2)//2):
        zeros.append([0]*i)
        if i:
            print(zeros[-1])

    for i in range(m + 1):
        makebag(i, i, 1, [])

    for ky in dic:
        for mm in range(1,m + 1):
            cmplmntry = (mm - ky[0], ky[1])
            if cmplmntry in dic:
                for plus in dic[ky]:
                    for y in dic[cmplmntry]:
                        minus = [-t for t in y]
                        for i in range((m - mm + 2) // 2):
                            print(minus + zeros[i] + plus)

makezero(12)
#print(dic)  # for reference

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

It is easy to do it quite efficient. Let's do two reductions to the common problem.

First we understand the structure of generating sets. Set contains zero or more 0's (let's call it Zeros set), Pos set, containing only positive numbers, and Neg set, containing only negative.

Notice that sums of numbers in Pos and in Neg (if every number negate) are equivalent. This follows from the fact that sum all numbers is zero.

The cool thing is that we can generate Zeros, Pos and Neg independently. Zeros set has one parameter to generate - the number of elements. But Pos and Neg have two -- number of elements and it's sum (the second are equal for both sets).

Assume we have M - our border, S is the sum of elements in Pos (thus (-S) in Neg), a, b and z are numbers of elements in Pos, Neg and Zeros respectively. Then the cost of our set is 2(a+b+c+S)<=M.

So, we can easilly manage the generation by tweaking these numbers.

Now let's generate all three sets independently (with constrains we found before) and union it. To generate Zeros set by parameter z we need...just do it.

Obviously, the generating Pos and Neg is similar, different only parameters a and b. And that is just a partition of numbers!

So, the naive solution is:

1. Get M
2. Generate all combinations of a, b, z, S, satisfying simple constraints (all are non-negative integers and 2(a+b+c+S)<=M)
3. By z generate Zeros = {0}^z
4. By a and S generate all partitions of S length a
5. for each a_i: partition from the previous step:
6. By b and S generate all partitions of S length a
7. yield Zeros + a_i + b_i

Despite this solution is naive, it is rather more efficient than generating all sets and filtering.

To boost-speedup-accelerate it let's see at this set as a number Pos_Zeros_Neg. It has only three digits -- our sets. And we will..increment it!

1. Generate a, b, z, S
2. init_pos <- {S}; init_neg <- {S}
3. initialize Pos, Zeros, Neg <- init_pos, {0}^z, init_neg
4. while has_next(Pos, a):
5. |......while has_next(Neg, b):
6. |......|......yield Zeros + Pos + {-Pos}
7. |......|......next(Neg, b)
8. |......Neg <- init_neg
9. |......next(Pos, a)

Where

• {-Pos} is a Pos set but all numbers are negated;
• next(Set, len) -- a function that generate lexicographically next partition of the Set, with length len;
• has_next(Set, len) -- checks if that set exists.

EDIT:

Here's a my .py file of the fast version

EDIT++

Here the full code:

def gen(n, leng):
    if leng == 0:
        yield []
        return
    if leng == 1:
        yield [n]
        return
    if leng > n:
        return

    s = [n - leng + 1]
    for i in range(leng - 1):
        s.append(1)
    s.append(-1)

    while True:
        yield s[:-1]

        if s[1] <= s[0] - 2:
            s[0] -= 1
            s[1] += 1
            continue

        ind = 2
        summ = s[0] + s[1] - 1
        while s[ind] >= s[0] - 1:
            summ += s[ind]
            ind += 1

        if ind >= leng:
            break

        x = s[ind] + 1
        s[ind] = x
        ind -= 1
        for i in range(ind, 0, -1):
            s[i] = x
            summ -= x
        s[0] = summ

def gen_abzs(m):
    m = m // 2
    for s in range(m + 1):
        for a in range(min(m-s, s) + 1):
            for b in range(min(m-s-a, a) + 1):
                if a == 0 and b == 0 and s > 0:
                    continue
                for z in range(m-s-a-b + 1):
                    if a == 0 and b == 0 and s == 0:
                        yield [a, b, z, s]
                        continue
                    if a == 0 and b != 0:
                        continue
                    if a != 0 and b == 0:
                        continue
                    yield [a, b, z, s]
                    if a != b:
                        yield [b, a, z, s]

def solve(m):
    for a,b,z,s in gen_abzs(m):
        zeros = [0] * z
        for pos in gen(s, a):
            for neg in gen(s, b):
                neg = list(map(lambda x:-x, neg))
                ans = zeros.copy()
                for i in pos:
                    ans.append(i)
                for i in neg:
                    ans.append(i)
                yield ans

def main():
    for s in solve(20):
        print(s)

if __name__ == '__main__':
    main()

Caveat: This is not provably the best algorithm. There are some duplicate checks that might be able to be removed. But it is a working solution without duplicate results.

Any absolute sum of non-zero integers with cost Q<M can be made to have cost M by adding (M-Q)/2 zeros to it. So, we can ignore anything with a 0 in it for now. We will generate all bags containing no zeros with cost <= M, and then add the appropriate number of 0s to make it cost M afterwards.

Additionally, we can simplify further by finding the set of bags that have a cost of M exactly. Then, to find all bags with <= M, we can just loop over all numbers up to M.

So, now our goal is to find a set of bags containing no zeros that have cost exactly M.

To make it easier, let's just consider how many ways we can select k numbers to make exactly M, and then loop over different k's. We can then assign some k to the positives, and some to the negatives, and ensure that they sum to the same value.

So, now we're looking for a way to find all partitions of n, but only of a particular length. Then there is a bag that satisfies the constraints for each possible pair of these partitions. I adapted the answer to the linked question, and put it together with the above reasoning to get:

import functools

@functools.lru_cache(maxsize=1024*1024)
def partitions_with_k(k, largest, *rest):
    '''
    Finds all partitions which sum to `largest`
    with precisely k elements in it
    '''
    result = [[largest, *rest]]
    if (rest and len(rest) == k-1 or k == 1):
        return result
    min = rest[0] if rest else 1
    max = largest // 2
    for n in range(min, max+1):
        result.extend(partitions_with_k(k, largest-n, n, *rest))
    result = [p for p in result if len(p) == k]
    return result

def get_bags_exact(M, a=1, b=2):
    '''
    Finds all bags without zeros with total cost exactly equal to M
    '''
    # let k be the number of integers in the bag.
    # The minimum cost of including a non-zero value is a*1+b,
    # therefore we only need to check k up to M//(a+b) (the +/-1 solution, if it exists)
    result = []
    min_cost = a+b
    for k in range(1, 1+M//min_cost):
        for kn in range(1, k):
            kp = k-kn
            # Let P be the positive sum of integers in the partition
            # M = a*P*2 + k*b
            P = (M-k*b)/(a*2)
            # Clearly we can only accept integer sums
            if P % 1 == 0:
                P = int(P)
                pos = partitions_with_k(kp, P)
                neg = partitions_with_k(kn, P)
                neg = [[-e for e in part] for part in neg]
                for partp in pos:
                    for partn in neg:
                        result.append(partp + partn)
    return result

def get_bags(M, a=1, b=2):
    ''' Finds all bags with cost M or less '''
    result = []
    n_zeros = (M)//b
    for i in range(n_zeros+1):
        result.append([0]*i)
    for Q in range(1, 1+M):
        n_zeros = (M-Q)//b
        exactlyQ = get_bags_exact(Q, a, b)
        for i in range(n_zeros+1):
            for bag in exactlyQ:
                result.append(bag+[0]*i)
    return result

A major benefit of using recursive functions in python is the ease with which you can cache results. So I will keep it as a recursive version, but you could make it iterative, if you wanted. I found that partitions_with_k wasn't really the bottleneck, anyway (see below).

I checked it manually up to M=14 and with a sanity check up to M=50:

bags = get_bags(50)
to_check = [tuple(sorted(b)) for b in bags]
assert len(to_check) == len(set(to_check))

Theoretically, this may be able to be improved inside partitions_with_k by not doing an explicit filter, and instead never ending up adding anything of the wrong length, but I think you'd have to know ahead of time how long all of the results would be. I'm not sure if it's possible. I can't see it. Perhaps you can.

Potentially, there's a good way to use the dual solutions: taking the negative of any bag is also a solution. Here, I don't explicitly use that at all.

Run-time complexity of get_bags without accounting for partitions_with_k is O(M^4). Before caching, partitions_with_k is O(M^2). So, roughly speaking, it's O(M^6). The sequence size grows reasonably quickly. It gets slow pretty quickly, and the memory cost is pretty big.

e.g. M=70 has ~9 million bags, took ~9.2s on my machine, and used up ~1.5GB of RAM while processing

I used cProfile to see where the time is actually spent. It's telling me that ~5.6s of those 9.2s, the interpreter was in get_bags, and only 0.14s is in partitions_with_k. I'm honestly not sure what's so slow in get_bags; adding all the solutions with 0s takes time, I guess?

$ python3 -m cProfile -s cumtime bags.py
9012501
         12069213 function calls (12004973 primitive calls) in 9.246 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    9.262    9.262 {built-in method builtins.exec}
        1    0.030    0.030    9.262    9.262 bags.py:1(<module>)
        1    5.670    5.670    9.233    9.233 bags.py:45(get_bags)
       70    2.949    0.042    3.222    0.046 bags.py:19(get_bags_exact)
 11704256    0.444    0.000    0.444    0.000 {method 'append' of 'list' objects}
64614/374    0.108    0.000    0.140    0.000 bags.py:3(partitions_with_k)
     2970    0.015    0.000    0.031    0.000 bags.py:39(<listcomp>)
    52305    0.019    0.000    0.024    0.000 bags.py:16(<listcomp>)
   180736    0.008    0.000    0.008    0.000 {built-in method builtins.len}
    64240    0.004    0.000    0.004    0.000 {method 'extend' of 'list' objects}

Your timings will vary based on hardware and versions of software, but the proportions were consistent when I ran this using a python:3.6 docker image, compared to my native python 3.6 install.