I wanted to make an accel asc algorithm that only outputs partitions that only have terms that are smaller than or equal to n. For example: if I want the partitions of 4, and n = 2, the wanted partitions are: (2,2),(2,1,1),(1,1,1,1).
This could be easily done by generating all of them then we just have to filter out the unwanted partitions, but that is too slow. I want this to be as efficient as possible. Can the algorithm itself be modified somehow so it doesnt even generate the unwanted partitions?
Here is the said algorithm:
def accel_asc(n: int,minLen: int = float("-inf"),maxLen: int = float("inf")):
a = [0 for i in range(n + 1)]
k = 1
y = n - 1
while k != 0:
x = a[k - 1] + 1
k -= 1
while 2 * x <= y:
a[k] = x
y -= x
k += 1
l = k + 1
while x <= y:
a[k] = x
a[l] = y
if minLen <= k + 2 <= maxLen:
yield a[:k + 2]
x += 1
y -= 1
a[k] = x + y
y = x + y - 1
if minLen <= k + 1 <= maxLen:
yield a[:k + 1]
I managed to modify it so it can generate partitions with a specific length range, this was really easy, but I really cant wrap my head around this.
I tried adding if x <= limit and y <= limit:
after line 15 and 22, and it seemed to almost work, but there were 1 or 2 partitions that contained bigger numbers than n. But I’m not sure how can I actually do this because I dont really understand how the algorithm works.
bborxx is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.