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