number generator

[Steven D'Aprano]

On Tue, 13 Mar 2007 23:08:38 -0800, Paul Rubin wrote:

> Steven D'Aprano <steve at REMOVEME.cybersource.com.au> writes:
>> > It should be possible to enumerate all sets of five numbers which sum
>> > to 50 and randomly select one of them.
>> 
>> Of course it's possible. It's also a very inefficient way of doing so. For
>> five numbers between 1 and 50, there are 50**5 = 312,500,000 possible sets
>> to enumerate. 
> 
> No there are only 2611 such sets and generating them takes about 0.5
> seconds on my laptop.  I posted the code for this elsewhere in the thread.

If you generate all the possible sets of five numbers between 1 and 50,
there are 50**5 of them, not 2611.

Naturally you don't have to store them all, and if you read what I wrote,
you'll see I never suggested that you have to store them all. That would
be silly. Of course you would use a generator.

Now that I've seen your _partition() function, I'm quite impressed. It is
still brute-force, but it avoids generating all 50**5 non-unique lists. By
my count, it only has to throw away 11,294 lists to generate the 2611
unique lists it returns.

And it is quite fast too: approximately 0.12 seconds on my PC.
Unfortunately, it doesn't scale. 

unique_partitions(60, 6) takes 0.8 seconds; unique_partitions(80, 8)
takes about 25 seconds; unique_partitions(80, 10) takes about 80 seconds,
and unique_partitions(81, 10) takes over 90 seconds.

So yes, your partition algorithm does avoid creating the millions of lists
which don't sum to 50, and that's a good thing. But it still brute-forces
thousands or millions of lists when only one is needed.

(E.g. unique_partitions(80, 10) returns 533,975 unique lists.
_partitions(80, 10) gives 3,233,568 non-unique lists.)



-- 
Steven D'Aprano