Ran into this issue in a programming challenge on HackerRank and I was surprised there weren’t any “simple” solutions online. The math related is mostly focused on finding the number of possible partitions of an integer, instead of generating even just one such partition.
A very naive approach might be to enumerate all partitions and then filter them down to those with exactly the wanted number of summands and then filter further to those with distinct parts and pick the first that fulfills the conditions.
But when the subject integer can be 1018 then that simply isn’t realistic. Insert sophisticated simile involving the heat death of the universe.
The problem I worked on had some useful restrictions. I couldn’t just use any number in the partition, only integers in the range 1 to a given k. This meant that I didn’t actually have to loop over that set and check for sums, I could use the arithmetic formula for range sum x*(x+1)/2. One tricky point was checking if x fit into 32 bit – otherwise x*x could overflow 64 bit, which in Clojure for example needs boxing with bigint.
There were also a bunch of conditions that could be “quickly” tested before starting to generate a partition. For example if I can only use 1 to k but the sum of 1 to k is less than the number they should sum up to, it’s clearly not possible. Similarly if I have to generate a partition of b items, but even the sum of 1 to b (the smallest sum possible with b distinct positive integers) is bigger than the desired sum it’s again not possible.
As for the algorithm itself, I decided to go down the usable range, pick the largest number and check if it’s possible to generate difference with the remaining number of parts. I go down the range because this way I can use the range shortcut and the math is simpler too (just sum 1 up to x). Also for very large numbers it felt better to reduce the upper limit (by subtracting each iteration) than working up to it one by one.
If the difference (desired sum – the picked number) is smaller than the minimum that can be generated (sum of 1 to the number of parts left), then it can’t be completed so I try again with the next number down the range.
If the difference is equal to the minimum, it’s a convenient shortcut: in Clojure I can just say (rest (range x)) for the range 1 to x instead of looping.
If the difference is larger than the minimum then I add the picked item to the array representing the partition and repeat. For the next loop the biggest to pick is the smaller of the difference and picked number – 1.
Memoizing this process means that “evil” test cases that invoke the same very big numbers 20 times can be processed relatively quickly. With very large numbers just returning (writing to file) the gigantic array generated can become an issue.
Once again this was the kind of problem that feels like some PhD student just copied it out of their textbook (in fact I found a reference online to a college textbook problem just like this). That’s why I kinda hoped that there would be some “smart” math formula for quickly generating one partition, but I could only find ways to generate the number of partitions.
Since I was using Clojure I wasn’t mutating stuff left and right, but a Python solution I found was generating the partition by incrementing items in the 1 to b range. I don’t know if it’s fast but surely didn’t look like it. With my method if accumulating the summands in an array becomes unfeasible, I could just write them out on the spot. With mutating I don’t think that’s possible.
