fork(1) download
copy 
  1. import random
  2.  
  3. def ModularSubsetSum(W, m):
  4.     p = 1234567891                            #large prime ${\color{commentcolour} p > m^2 \log m}$
  5.     r = random.randint(0,p)                   #random number ${\color{commentcolour} r}$ in [0,p)
  6.     powr = [1]                                #Precompute powers of ${\color{commentcolour} r }$
  7.     for i in range(2*m):                      #powr[i] ${\color{commentcolour} \triangleq }$ ${\color{commentcolour} r^i }$ (mod p)
  8.         powr.append((powr[-1] * r) % p)
  9.  
  10.  
  11.     #Binary Indexed Tree for prefix sums
  12.     tree = [0] * (2*m)
  13.     def read(i):                              #Prefix sum of [0,i)
  14.         if i<=0: return 0
  15.         return tree[i-1] + read(i-(i&-i)) 
  16.     def update(i, v):                         #add v to position i
  17.         while i < len(tree):
  18.             tree[i] += v
  19.             i += (i+1)&-(i+1)
  20.  
  21.  
  22.     #Functions for finding new subset sums and adding them
  23.     def FindNewSums(a,b,w):
  24.         h1 = (read(b)-read(a))*powr[m-w] % p  #hash of ${\color{commentcolour} S \cap [a,b)}$
  25.         h2 = (read(b+m-w)-read(a+m-w)) % p    #hash of ${\color{commentcolour} (S+w) \cap [a,b)}$
  26.         if h1 == h2: return []
  27.         if b == a+1:                        
  28.             if sums[a] is None: return [a]    #a is a new sum
  29.             return []                         #a is a ghost sum
  30.         return FindNewSums(a,(a+b)//2,w) + FindNewSums((a+b)//2,b,w)
  31.     def AddNewSum(s, w):
  32.         sums[s] = w
  33.         update(s,powr[s]), update(s+m,powr[s+m])
  34.  
  35.  
  36.     #Main routine for computing subset sums
  37.     sums = [None] * m
  38.     AddNewSum(0,0)
  39.     for w in W:
  40.         for s in FindNewSums(0,m,w):
  41.             AddNewSum(s,w)
  42.  
  43.     return sums
  44.  
  45. print(ModularSubsetSum([1,3,6], 8))  #Returns [0, 1, 6, 3, 3, None, 6, 6]
  46.  
  47. def RecoverSubset(sums, s):
  48.     if sums[s] is None: return None
  49.     if s <= 0: return []
  50.     return RecoverSubset(sums, (s-sums[s]) % len(sums)) + [ sums[s] ]
  51.  
  52. sums = ModularSubsetSum([1,3,6], 8)
  53. print(RecoverSubset(sums, 7))  #Returns [1, 6]
  54. print(RecoverSubset(sums, 2))  #Returns [1, 3, 6]
Success #stdin #stdout 0.03s 65936KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[0, 1, 6, 3, 3, None, 6, 6]
[1, 6]
[1, 3, 6]
https://ideone.com/YlLwMQ
language:
Python (PyPy 2.7.13)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!