Subset sum

description.md

This is demo code for the journal version of the faster subset sum paper.

Konstantinos Koiliaris and Chao Xu. 2019. Faster Pseudopolynomial Time Algorithms for Subset Sum. ACM Trans. Algorithms 15, 3, Article 40 (July 2019), 20 pages. DOI:https://doi.org/10.1145/3329863

subset_sum.py

from numpy import nonzero, select, zeros
from scipy.signal import fftconvolve
from operator import itemgetter
import math

# to test, try the following
# > import random
# > xs = list(set(random.sample(range(10000), 500)))
# > SS_SmallInput(xs,50000) == naive_subset_sums_up_to_u(xs,50000)

def naive_subset_sums_up_to_u(xs,u):
    sums = set([0])
    for x in xs:
        sums2 = set(sums)
        for y in sums:
            if x+y<u :
                sums2.add(x+y)
        sums = sums2
    return sums

eps = 0.0001

# given two lists of elements (1d or 2d), and upper bound on the first coorindate u, do minkowski sum
def minkowski_sum(a, b, u):

  def minkowski_sum_1D(a, b, u):
    result = minkowski_sum_2D([(x, 0) for x in a], [(x, 0) for x in b], u)
    return [x for (x, _) in result]

  def minkowski_sum_2D(a, b, u):
    def L2M(S):
      # list to matrix representation
      c1 = list(map(itemgetter(0), S))
      c2 = list(map(itemgetter(1), S))
      M = zeros((max(c1) + 1, max(c2) + 1))
      M[c1, c2] = 1
      return M

    def M2L(M):
      # matrix to list representation
      return zip(*nonzero(select([M > eps], [1])))

    conv = fftconvolve(L2M(a), L2M(b))
    return [(x, y) for (x, y) in M2L(conv) if x < u]

  if type(a[0]) is tuple:
    return minkowski_sum_2D(a, b, u)
  else:
    return minkowski_sum_1D(a, b, u)

# input is a list of *distinct* non-negative integers S, u is an upper bound
# output all subset sums of S up to u together with the cardinality information
def SSC_BoundSum(S,u):
  if len(S)==1:
    return [(0,0), (S[0],1)]
  return minkowski_sum(SSC_BoundSum(S[0::2], u), SSC_BoundSum(S[1::2], u), u)

# input is a list of *distinct* non-negative integers S, u is an upper bound
# output all subset sums of S up to u, as a set. 
def SS_SmallInput(S, u):
  n = len(S)
  b = int(math.sqrt(n * math.log(n)))
  # compute S_l, need to do this in a single loop in order to do partition in linear time.
  partitioned_S = dict()
  for x in S:
    if x % b not in partitioned_S:
      partitioned_S[x % b] = []
    partitioned_S[x % b].append(x)
  result = [0]
  for l in range(b):
    Q_l = [x//b for x in partitioned_S[l]]
    R_l = [z*b+l*j for (z,j) in SSC_BoundSum(Q_l, u//b)]
    result = minkowski_sum(result, R_l, u)
  return set(result)

Hi Chao.

Line 72 contains an error, it should u // b + 1. Otherwise you might leave a value out!

Best,
Mikkel.