On Tue, 13 Mar 2007 23:08:38 -0800, Paul Rubin wrote: > Steven D'Aprano <[EMAIL PROTECTED]> 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 -- http://mail.python.org/mailman/listinfo/python-list
