Skip to content

Instantly share code, notes, and snippets.

@gilleain
Created May 18, 2009 11:15
Show Gist options
  • Save gilleain/113422 to your computer and use it in GitHub Desktop.
Save gilleain/113422 to your computer and use it in GitHub Desktop.
def EnumPartitions(m, n):
P = {(0, 0) : 1}
for i in range(1, m + 1):
P[(i, 0)] = 0
for i in range(1, m + 1):
for j in range(1, min(i, n) + 1):
if i < 2 * j:
P[(i, j)] = P[(i - 1, j - 1)]
else:
P[(i, j)] = P[(i - 1, j - 1)] + P[(i - j, j)]
return P
def PartitionLexUnrank(m, n, r):
P = EnumPartitions(m, n)
a = [0] * n
while m > 0:
if r < P[(m - 1, n - 1)]:
a[n - 1] = a[n - 1] + 1
m = m - 1
n = n - 1
else:
for i in range(0, n):
a[i] = a[i] + 1
r = r - P[(m - 1, n - 1)]
m = m - n
return a
def getPartitions(num, parts):
l = EnumPartitions(num, parts)[num, parts]
return [PartitionLexUnrank(num, parts, rank) for rank in range(0, l)]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment