For this post I’ll look at slight variation where a maximum value can be set.
In that case, some of the combinations need to be excluded.
For example for $n=5$ and a maximum value of $3$, the top two ways are excluded.
The previous blog post The Birthday Problem: Advanced required something a little more complicated: integer partitions but bounded by certain values at each index.
For example, select 5 people from 3 teams where there are 2 people in the first team, 1 person in the second team, and 5 or more people in the third team. Here the partitions are:
Note that in this problem permutations are distinct from each other, unlike the first problem.
The rest of this post will detail algorithms for these in Julia code.
Recursion
Counting
Define $p(n)$ as the count of integer partitions of $n$. Then $p(n) = \sum_{k=1}^n p(n - k)$.
This can readily be converted into a recursive formula:
The bounded version requires the slight modification of keeping track of the index so that the correct maximum can be selected.
It also includes a zero case.
Integer partitions
We can modify the counting formula to instead return arrays.
Then we can return the whole set of arrays.
In Python you can use the yield keyword to return each partition one at a time.
Unfortunately you cannot do that in Julia, but changing to a linear algorithm we can get the same behaviour.
See the Linear integer partitions section.
Bounded partitions
For the bounded version we can do a similar modification to its counting function:
Caching can be added to improve the performance.
Linear
Integer partitions
We can also write these functions in linear stateful versions.
With this technique we don’t have to hold the whole array of all partitions in memory.
(In Python you could use the yield keyword to accomplish this.)
The state is the last partition and the current index of the value that is being decremented.
We could use the count_integer_partitions function to get the length.
But because this requires some computation, it is better to set the size as Base.SizeUnknown().
Next, we iterate through the partitions as before.
But this time instead of jumping to a new function call, we move an index up and down (like a pointer).
Example:
Bounded partitions
The struct is similar to before.
We will set the maximum of max_values to n here.
The iterations require a few subtle modifications.
Parts which are not modified are not shown.