Integer partitions is a very interesting topic. Creating all the partitions of a given integer is almost simple, such as the following code:
def aP(n)
a = [1]*n
y = -1
v = n
while v > 0:
v -= 1
x = a[v] + 1
while y >= 2 * x:
a[v] = x
y -= x
v += 1
w = v + 1
while x <= y:
a[v] = x
a[w] = y
yield a[:w + 1]
x += 1
y -= 1
a[v] = x + y
y = a[v] - 1
yield a[:w]
Searching for a way to gain much more control over the function, for example in order to generate only the partitions of N size, this solution appears better:
def sum_to_n(n, size, limit=None)
if size == 1:
yield [n]
return
if limit is None:
limit = n
start = (n + size - 1) // size
stop = min(limit, n - size + 1) + 1
for i in range(start, stop):
for tail in sum_to_n(n - i, size - 1, i):
yield [i] + tail
But both of them do generates ALL the possible partitions of the given number, the first with every size, the second of the given size. What if I want only one specific partition of a given number ? The following code generates the next partition of a given partition:
def next_partition(p):
if max(p) == 1:
return [sum(p)]
p.sort()
p.reverse()
q = [ p[n] for n in range(len(p)) if p[n] > 1 ]
q[-1] -= 1
if (p.count(1)+1) % q[-1] == 0:
return q + [q[-1]]*((p.count(1)+1) // q[-1])
else:
return q + [q[-1]]*((p.count(1)+1) // q[-1]) + [(p.count(1)+1) % q[-1]]
But still there is a problem, you have to know what is the partition before the partition requested.
Suppose now to need a given partition of an integer N and you only know the number of the partition; example:
The partitions of 4 are:
n.1 4
n.2 3+1
n.3 2+2
n.4 2+1+1
n.5 1+1+1+1
How to create the partition number 2 (3+1) giving only the integer (4), the sequence number (2) and optional the size ? All of this without the creation of all the partitions ? I have read somewhere that is possible with a mathematic formula but I do not know how.
What I have tried:
Studied a lot of textbooks about the topic but I've not reached the solution.