Commits

Roger Pate  committed e28513c

add greplin-challenge/subsets2.py

  • Participants
  • Parent commits 10b83af

Comments (0)

Files changed (2)

File greplin-challenge/subsets.py

 #!/usr/bin/env python2.6
+"""Subsets
+
+This is a naive solution which brute forces all subsets.  I verified it gave the correct results, then didn't think any more of it.
+"""
 
 import sys
 import itertools

File greplin-challenge/subsets2.py

+#!/usr/bin/env python2.6
+"""Subsets
+
+This is a dynamic solution which runs efficiently.  I did not think of this approach, but implemented it from the description at http://programmingpraxis.com/2010/11/09/subset-sums/.
+"""
+
+def solve(numbers):
+  """Solve sum of subsets for numbers.
+
+  numbers must be positive and in sorted order.
+  """
+  memo = {}
+  def f(stop, target):
+    """number of subsets of numbers[:stop] which sum to target"""
+    if stop == 0:  # empty set only matches if target is 0
+      return target == 0
+    if target == 0:  # only empty set matches
+      return 1
+
+    key = (stop, target)
+    if key in memo:
+      return memo[key]
+
+    result = f(stop - 1, target)  # without last
+    last = numbers[stop - 1]
+    if target >= last:
+      result += f(stop - 1, target - last)  # with last
+
+    memo[key] = result
+    return result
+
+  return sum(f(x, numbers[x]) for x in xrange(2, len(numbers)))
+
+
+def show(numbers):
+  print numbers
+  print "=", solve(numbers)
+  print
+
+show([1, 2, 3, 4, 6])
+show([3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99])
+
+
+# primes example from Praxis
+
+def primes(stop):
+  """Return sieve for primes 2..stop."""
+  sieve = [True] * stop
+  for x in xrange(2, stop):
+    if sieve[x]:
+      yield x
+      for n in xrange(2 * x, stop, x):
+        sieve[n] = False
+
+show(list(primes(2**10)))