Re^2: Decomposing sum to unique sets of summands

The post says:

And this needs to be very fast since in use it's going to have to handle sums of up to 10^6.

I don’t think your program can be used for this; it only works for small integers.

The so-called partition function p(n) represents the number of possible partitions of a natural number n (distinct and order independent). Unfortunately p(n) grows rapidly, see Partition. Try to run the program on n=1000.

Comment on Re^2: Decomposing sum to unique sets of summands

Replies are listed 'Best First'.
Re^3: Decomposing sum to unique sets of summands by JavaFan (Canon) on Oct 28, 2008 at 15:00 UTC
Yes, I don't claim it's fast. And I don't think you can do it fast in Perl - you'll have to use some C or other fast language. And even then, you'd still have to convert all the numbers back into Perl numbers to process them. For the interested, the number of such partitions is A083751 in the OEIS.	[reply]
Re^3: Decomposing sum to unique sets of summands by JadeNB (Chaplain) on Oct 28, 2008 at 17:54 UTC
I don’t think your program can be used for this; it only works for small integers. It seems unfair to call this a problem with JavaFan's solution. As you point out, the bottleneck is mathematical—there are so many partitions—rather than programmatic, so any program that does what the poster seems to want will be slow on large numbers. Maybe the poster only needs a few partitions, or knows something about the data-sets, so that some optimisations can be applied?	[reply]