number generator

Dick Moores rdm at rcblue.com
Tue Mar 13 08:37:56 CET 2007


At 06:38 AM 3/10/2007, Steven D'Aprano wrote:
>On Sat, 10 Mar 2007 02:32:21 -0800, Dick Moores wrote:
>
> > So why not just repeatedly call a function to generate lists of
> > length N of random integers within the appropriate range (the closed
> > interval [1,M-N-1]), and return the first list the sum of which is M?
> > I don't understand what all the discussion is about. Time is not one
> > of the constraints.
>
>Time is always a constraint. The sun will expand and destroy the Earth in
>a couple of billion years, it would be nice to have a solutions before
>then...
>
>*wink*
>
>Seriously, almost all programming problems have two implicit constraints:
>it must run as fast as practical, using as little computer resources (e.g.
>memory) as practical. Naturally those two constraints are usually in
>opposition, which leads to compromise algorithms that run "fast enough"
>without using "too much" memory.

OK, points well-taken.

The problem posed by the OP is "Given two positive integers, N and M 
with N < M, I have to generate N
positive integers such that sum(N)=M. No more constraints."

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].

Wouldn't sumRndInt() be THE solution?:
=================================================================
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

if __name__ == '__main__':

     N = 5
     M = 50

     lst = sumRndInt(M, N)

     print "N is %d, M is %d, lst is %s, sum(lst) is %d" % (N, M, 
lst, sum(lst))
==============================================================

I hope I don't seem querulous--I really want to know.

Thanks,

Dick Moores






More information about the Python-list mailing list