Problem set
This is somewhat a generalization of the famous partition of integer n into k parts.
Given two integers a,b I need to find the number of partitions into k distinct parts that sum up to (a,b). E.g if (a,b)=(4,6) and k=2 we have q(a,b,k)=7 since the following are partitions:
((1, 1) + (3, 5))((1, 2) + (3, 4))((1, 3) + (3, 3))((1, 4) + (3, 2))((1, 5) + (3, 1))((2, 1) + (2, 5))((2, 2) + (2, 4))
Notice that partition ((2, 3) + (2, 3)) is not taken into account since the parts are the same and each partition is counted once (meaning ((2, 2) + (2, 4)) and ((2, 4) + (2, 2)) are one and the same partition.
My solution
class Partition_2D_K_PARTS:
def __init__(self, a, b, k) -> None:
self.q_a_b_k = 0 # counts q(a,b,k)
self.stack_partition = collections.deque() # represent a partition
self.calculate_partitions_for_single(a, b, k)
def calculate_partitions_for_single(self, c, d, k):
if (k==1):
if (c==0 or d==0):
return
last_part = (c,d)
second_to_last_part = (1, 0) if not self.stack_partition else self.stack_partition[-1]
if (second_to_last_part < last_part):
self.q_a_b_k += 1
return
else:
return
second_to_last_part = (1, 0) if not self.stack_partition else self.stack_partition[-1]
for j in range(second_to_last_part[1] + 1, d+1):
i = second_to_last_part[0]
self.stack_partition.append((i, j))
self.calculate_partitions_for_single(c-i, d-j, k-1)
self.stack_partition.pop()
for i in range(second_to_last_part[0] + 1, c+1):
for j in range(1, d+1):
self.stack_partition.append((i, j))
self.calculate_partitions_for_single(c-i, d-j, k-1)
self.stack_partition.pop()
My question is ...
As you can see my solution is using recursion (which is not very effective). I want to improve the runtime (convert it to iterative solution or something else.) but I don't quite sure how. Also, I don't want to use too much space since I want to use the function on very large numbers. I would like your help and thoughts on this problem.