Skip to content

Instantly share code, notes, and snippets.

@zpconn

zpconn/partition.py

Created January 14, 2014 02:33
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save zpconn/8412059 to your computer and use it in GitHub Desktop.
Save zpconn/8412059 to your computer and use it in GitHub Desktop.
Download ZIP
This solves a simplified version of the partition problem in polynomial time. Namely, given a list, this finds a pair of sublists of equal length whose sums are the same.
Raw
partition.py
def sublists(a, n):
if n == 0:
return [[]]
elif len(a) == 0:
return []
else:
return sublists(a[1:], n) + [[a[0]] + s for s in sublists(a[1:], n - 1)]
def partition(a):
if len(a) % 2 != 0:
return None
halves = sublists(a, len(a) / 2)
total = sum(a)
for half in halves:
if sum(half) == total / 2:
other_half = list(a)
for x in half:
other_half.remove(x)
return (half, other_half)
return None
print partition([3, 1, 1, 2, 2, 1, 4, 9, 3, 2, 9, 1])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment