number generator

[Dick Moores]

At 02:52 AM 3/13/2007, Duncan Booth wrote:
>Dick Moores <rdm at rcblue.com> wrote:
>
> > But let's say there is one more constraint--that for each n of the N
> > positive integers, there must be an equal chance for n to be any of
> > the integers between 1 and M-N+1, inclusive. Thus for M == 50 and N
> >== 5, the generated list of 5 should be as likely to be [1,46,1,1,1]
> > as [10,10,10,10,10] or [14, 2, 7, 1, 26].
>
>I don't think what you wrote actually works. Any combination including a 46
>must also have four 1s, so the digit 1 has to be at least 4 times as likely
>to appear as the digit 46, and probably a lot more likely than that.

Yes, I see you're right. Thanks.

>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. Of course, 
[1,46,1,1,1] and [1,1,46,1,1], as Python lists, are distinct. I ran 
this test for M == 8 and N == 4:
======================================================
def sumRndInt(M, N):
     import random
     while True:
         lst = []
         for x in range(N):
             n = random.randint(1,M-N+1)
             lst.append(n)
         if sum(lst) == M:
             return lst

A = []
B = []
for x in range(100000):
     lst = sumRndInt(8,4)
     if lst not in A:
         A.append(lst)
         B.append(1)
     else:
         i = A.index(lst)
         B[i] += 1

A.sort()
print A
print B
print len(A), len(B)
===========================================================
a typical run produced:
[[1, 1, 1, 5], [1, 1, 2, 4], [1, 1, 3, 3], [1, 1, 4, 2], [1, 1, 5, 
1], [1, 2, 1, 4], [1, 2, 2, 3], [1, 2, 3, 2], [1, 2, 4, 1], [1, 3, 1, 
3], [1, 3, 2, 2], [1, 3, 3, 1], [1, 4, 1, 2], [1, 4, 2, 1], [1, 5, 1, 
1], [2, 1, 1, 4], [2, 1, 2, 3], [2, 1, 3, 2], [2, 1, 4, 1], [2, 2, 1, 
3], [2, 2, 2, 2], [2, 2, 3, 1], [2, 3, 1, 2], [2, 3, 2, 1], [2, 4, 1, 
1], [3, 1, 1, 3], [3, 1, 2, 2], [3, 1, 3, 1], [3, 2, 1, 2], [3, 2, 2, 
1], [3, 3, 1, 1], [4, 1, 1, 2], [4, 1, 2, 1], [4, 2, 1, 1], [5, 1, 1, 1]]

[2929, 2847, 2806, 2873, 2887, 2856, 2854, 2825, 2847, 2926, 2927, 
2816, 2816, 2861, 2919, 2820, 2890, 2848, 2898, 2883, 2820, 2820, 
2829, 2883, 2873, 2874, 2891, 2884, 2837, 2853, 2759, 2761, 2766, 2947, 2875]

35 35

Dick Moores