number generator

[Duncan Booth]

Dick Moores <rdm at rcblue.com> wrote:

>>On the other hand, making sure that each combination occurs equally
>>often (as your example might imply) is doable but still leaves the
>>question whether the order of the numbers matters: are [1,46,1,1,1]
>>and [1,1,46,1,1] the same or different combinations?
> 
> If the added constraint is instead that the probability of generating 
> a given list of length N be the same as that of generating any other 
> list of length N, then I believe my function does the job.

I believe you are correct about the distribution. Unfortunately the 
running time for sumRndInt seems to go up exponentially as it gets stuck 
in that while loop desperately trying to find a random sequence that 
fits. 

C>timeit.py -s"from test import sumRndInt" "sumRndInt(50,4)"
100 loops, best of 3: 5.23 msec per loop

C>timeit.py -s"from test import sumRndInt" "sumRndInt(50,5)"
10 loops, best of 3: 21.8 msec per loop

C>timeit.py -s"from test import sumRndInt" "sumRndInt(50,6)"
10 loops, best of 3: 108 msec per loop

C>timeit.py -s"from test import sumRndInt" "sumRndInt(50,7)"
10 loops, best of 3: 861 msec per loop

C>timeit.py -s"from test import sumRndInt" "sumRndInt(50,40)"
... still waiting ...

By comparison, the algorithm using sorted(sample(...)) finishes quickly 
for all input values and also gives a flat distribution:

C>timeit.py -s"from partition import partition" "partition(50,4,1)"
100000 loops, best of 3: 20.2 usec per loop

C>timeit.py -s"from partition import partition" "partition(50,5,1)"
10000 loops, best of 3: 23 usec per loop

C>timeit.py -s"from partition import partition" "partition(50,6,1)"
10000 loops, best of 3: 25.2 usec per loop

C>timeit.py -s"from partition import partition" "partition(50,7,1)"
10000 loops, best of 3: 29.6 usec per loop

C>timeit.py -s"from partition import partition" "partition(50,40,1)"
10000 loops, best of 3: 100 usec per loop