number generator

[Steven D'Aprano]

Re: number generator

On Fri, 09 Mar 2007 18:41:39 +0000, Dennis Lee Bieber wrote:

On 9 Mar 2007 06:44:01 -0800, "cesco" <fd.calabrese@g mail.comdeclaim ed
the following in comp.lang.pytho n:
>

>I have to generate a list of N random numbers (integer) whose sum is
>equal to M. If, for example, I have to generate 5 random numbers whose
>sum is 50 a possible solution could be [3, 11, 7, 22, 7]. Is there a
>simple pattern or function in Python to accomplish that?
>>

Well... Just that the last number is not random -- it has to equal
(using your limit of 50 and 5 numbers):
>
fifth = 50 - sum(first, second, third, fourth)

Doesn't mean that it isn't random. After all, the first four numbers are
random, therefore their sum is random. 50 - (something random) is also
random.

In practice, one would deterministical ly generate the last number needed,
but that last number is unpredictable because the first four numbers are
unpredictable.

Remember that random numbers are not necessarily unconstrained, nor are
they necessarily uniformly distributed. We blithely talk about "random
numbers", but of course there is a constraint that we're selecting from a
finite range. Any finite range of numbers, no matter how big, is a
vanishingly small percentage of all the possible numbers.



--
Steven.

[Anton Vredegoor]

Re: number generator

Raymond Hettinger wrote:

To make the solutions equi-probable, a simple approach is to
recursively enumerate all possibilities and then choose one of them
with random.choice() .

Maybe it is possible to generate the possibilities by an indexing
function and then use randint to pick one of them. I suppose this is
like the bricks and bins problem this thread was about:

http://groups.google.nl/group/comp.lang.python/browse_thread/thread/4782b54fa39b3bad

Except that the bins now have at least 1 brick in them (if we have
positive numbers).

I posted a rather simplistic solution (but working I think) after Steven
Taschuk made some insightful remarks. I believe it is possible to
generate the list of numbers directly instead of permuting a list of '0'
and '1' characters and then finding the positions of the '1' elements.

A.

[Paul Rubin]

Re: number generator

Steven D'Aprano <steve@REMOVE.T HIS.cybersource .com.auwrites:

Doesn't mean that it isn't random. After all, the first four numbers are
random, therefore their sum is random. 50 - (something random) is also
random.

What does it mean for the first 4 numbers to be random? For example,
is 27 random?

By your method, what is the probability of the first number being
higher than 30? What is the probability of the fifth number being
higher than 30? If these probabilities are unequal, can we really say
the sequences are random?

[Mel Wilson]

Re: number generator

Gerard Flanagan wrote:

On Mar 9, 4:17 pm, "cesco" <fd.calabr...@g mail.comwrote:

>On Mar 9, 3:51 pm, Paul Rubin <http://phr...@NOSPAM.i nvalidwrote:
>>

>>"cesco" <fd.calabr...@g mail.comwrites:
>>>I have to generate a list of N random numbers (integer) whose sum is
>>>equal to M. If, for example, I have to generate 5 random numbers whose
>>>sum is 50 a possible solution could be [3, 11, 7, 22, 7].

>
Suppose you have a fixed telegraph pole at N and a fixed telgraph pole
at M, and you're given 5 more telegraph poles...
>

That's a good one! Three-liner.

Cheers, Mel.

[Paulo da Silva]

Re: number generator

cesco escreveu:

I have to generate a list of N random numbers (integer) whose sum is
equal to M. If, for example, I have to generate 5 random numbers whose
sum is 50 a possible solution could be [3, 11, 7, 22, 7]. Is there a
simple pattern or function in Python to accomplish that?
>
Thanks and regards
Francesco
>

May be this is what you want ...
I didn't test it enough ... but seems fine.

from random import randint,shuffle

def GenRInt(m,n):
"""Generate m positive ints whose sum is n"""
# Generate a random list
xl=[randint(1,n-m+1) for i in xrange(m)]
s=sum(xl)
if s==n: return xl
# Adjust each value to make sum==n
xl=[max(x*n/s,1) for x in xl]
s=sum(xl)
if s!=n:
# Compensate for truncations
if s>n:
# s>n is supposed not to occur. Just in case ...
ixs=filter(lamb da x: xl[x]>1,range(m))
shuffle(ixs)
for i in ixs[:s-n]: xl[i]-=1
else:
ixs=range(m)
shuffle(ixs)
for i in ixs[:n-s]: xl[i]+=1
return xl

# Test it ...

xl=GenRInt(10,5 0)
print xl,"->",sum(xl)

print

xl=GenRInt(100, 10000)
print xl,"->",sum(xl)

print

xl=GenRInt(1000 ,1000)
print xl,"->",sum(xl)


Regards.
Paulo

[Paul Rubin]

Re: number generator

Paulo da Silva <psdasilvaX@eso tericaX.ptXwrit es:

May be this is what you want ...
I didn't test it enough ... but seems fine.

That's way too complicated. Think about Gerald Flanagan's description
of the telegraph poles, and how to implement simply. It is a two liner.

[Terry Reedy]

Re: number generator


"Anton Vredegoor" <anton.vredegoo r@gmail.comwrot e in message
news:esukru$1v1 $1@news2.zwoll1 .ov.home.nl...
| Raymond Hettinger wrote:
|
| To make the solutions equi-probable, a simple approach is to
| recursively enumerate all possibilities and then choose one of them
| with random.choice() .
|
| Maybe it is possible to generate the possibilities by an indexing
| function and then use randint to pick one of them. I suppose this is
| like the bricks and bins problem this thread was about:
|
|

http://groups.google.nl/group/comp.lang.python/browse_thread/thread/4782b54fa39b3bad

|
| Except that the bins now have at least 1 brick in them (if we have
| positive numbers).
|
| I posted a rather simplistic solution (but working I think) after Steven
| Taschuk made some insightful remarks. I believe it is possible to
| generate the list of numbers directly instead of permuting a list of '0'
| and '1' characters and then finding the positions of the '1' elements.

Partitioning positive count m into n positive counts that sum to m is a
standard combinatorial problem at least 300 years old. The number of such
partitions, P(m,n) has no known exact formula but can be computed
inductively rather easily. The partitions for m and n can be ranked in
lexicographic order from 0 to P(m,n)-1. Given a rank r in that range, one
can calculate the particular partition that has that rank. So a
equi-probable random count in the range can be turned into a equi-probable
random partition.

This topic is section 3.1 in Combinatorial Algorithms: Generation,
Enumeration, and Search by Kreher and Stinson. The authors reference
several other books as their sources.

I plan to someday rewrite many of their pseudocode algorithms in Python.

Terry Jan Reedy

[Anton Vredegoor]

Re: number generator

Terry Reedy wrote:

Partitioning positive count m into n positive counts that sum to m is a
standard combinatorial problem at least 300 years old. The number of such
partitions, P(m,n) has no known exact formula but can be computed
inductively rather easily. The partitions for m and n can be ranked in
lexicographic order from 0 to P(m,n)-1. Given a rank r in that range, one
can calculate the particular partition that has that rank. So a
equi-probable random count in the range can be turned into a equi-probable
random partition.

Yes that was one of my first ideas too. But later on Steven pointed out
that one can view the problem like this:

000100001000101 00

That would be [3,4,3,1,2]

where the '1' elements are like dividing shutters that partition the row
of '0'. This means that the problem is reduced to permutations (albeit
unique permutations) which are a lot simpler to compute than partitions.

Ok I'll admit that I succeeded in translating my 'Goldberg' solution to
this case, I can't expect anyone to dust off and read 4 year old threads
anyway :-)

(by the way I'm still convinced that this code can be simplified a lot)

def starters(L):
n,np,R = len(L),1,range( len(L))
bf = [L[:i].count(L[i]) for i in R]
for i in R: np = np*(n-i)/(bf[i]+1)
return [(i,np*L[i:].count(L[i])/n) for i in R if not bf[i]]

def perm(index,L):
remain,n = index,len(L)
res,T = L[:],L[:]
for i in range(n):
for j,k in starters(T):
if remain-k < 0:
res[i] = T.pop(j)
break
remain -= k
return res

def nperm(L):
return reduce(lambda a,b:a+b,[k for j,k in starters(L)])

def bb(i,bricks,bin s):
L = [1] * (bins-1) + [0] * (bins-1)
R = [1]
for x in perm(i,L):
if x: R.append(1)
else: R[-1]+=1
return R

def test():
bricks,bins = 7, 4
L = [1] * (bins-1) + [0] * (bins-1)
for i in range(nperm(L)) :
print bb(i,bricks,bin s)

if __name__=='__ma in__':
test()

This topic is section 3.1 in Combinatorial Algorithms: Generation,
Enumeration, and Search by Kreher and Stinson. The authors reference
several other books as their sources.

Great book!

I plan to someday rewrite many of their pseudocode algorithms in Python.

That would be my dream job. If only I understood more of them. But I'm
slowly making progress in other areas so that one day I will maybe
reread the book and also understand the second half.

A.

[Steven D'Aprano]

Re: number generator

On Sat, 10 Mar 2007 08:29:09 -0800, Paul Rubin wrote:

Steven D'Aprano <steve@REMOVE.T HIS.cybersource .com.auwrites:

>Doesn't mean that it isn't random. After all, the first four numbers are
>random, therefore their sum is random. 50 - (something random) is also
>random.

>
What does it mean for the first 4 numbers to be random? For example,
is 27 random?

In isolation, no, but 27 could have been chosen at random and hence would
have been unpredictable. That was my point: if we generate four
unpredictable numbers (using random.randint or similar) and sum them, the
sum is also unpredictable, and hence the difference between 50 and that
sum is unpredictable.

By your method, what is the probability of the first number being
higher than 30? What is the probability of the fifth number being
higher than 30? If these probabilities are unequal, can we really say
the sequences are random?

Of course we can! "Uniform probability distribution" is a special case of
random. Most random quantities are far from uniform. The Python random
module includes a couple of non-uniform distributions, including
exponential distribution (random.expovar iate) and the famous bell curve
distribution (random.normalv ariate).

One common distribution which seems to have been missed is the Poisson
distribution, which applies to (among many, many others) the number of
18th Century Prussian cavalry officers who fell off their horse and broke
a limb, and the number of cars arriving at a petrol station in any hour.



--
Steven.

[Anton Vredegoor]

Re: number generator

Anton Vredegoor wrote:

L = [1] * (bins-1) + [0] * (bins-1)

replace these lines in the code by:

L = [1] * (bins-1) + [0] * (bricks-bins)

A.

[Paul Rubin]

Re: number generator

Steven D'Aprano <steve@REMOVE.T HIS.cybersource .com.auwrites:

By your method, what is the probability of the first number being
higher than 30? What is the probability of the fifth number being
higher than 30? If these probabilities are unequal, can we really say
the sequences are random?

>
Of course we can! "Uniform probability distribution" is a special case of
random. Most random quantities are far from uniform. The Python random
module includes a couple of non-uniform distributions, including
exponential distribution (random.expovar iate) and the famous bell curve
distribution (random.normalv ariate).

Ehh. Say we call some generator repeatedly and get back the sequence
(3, 3, 3, 3, 3, ...). Would we say this is a random sequence using a
distribution that puts 100% of the probability density at 3? Or would
we just say it isn't random?

For something like this partition problem, describing some generator
as making a random partition should contain some reasonable
description of the distribution. For example, we could say the
generator selects one of the P(n) possible partitions with equal
probability. For another, we could say it uses the "fencepost" method
and the distribution is whatever results from that. Question then is
whether those two distributions are the same.

[MonkeeSage]

Re: number generator

On Mar 10, 3:16 am, greg <g...@cosc.cant erbury.ac.nzwro te:

Another possibility is to generate a list of N non-random
numbers that sum to M, and then adjust them up or down
by random amounts. By performing up/down adjustments in
pairs, you can maintain the sum invariant at each step.
So then it's just a matter of how long you want to go
on fiddling with them.

Taking your comment and running with it...this is pretty much
cheating, and requires that M be evenly divisible by N, and only works
well with smaller N values, and selections are limited to numbers in
the 1 to (M/N)+(M/N) range...but hey; other than that it's perfect,
heh.

import random
N, M = 10, 80
D = M/N
O = [D] * N
C = []
for i in O:
C.append(random .randint(1, D-1))
for i in range(0, len(O), 2):
O[i] -= C[i]
if i == len(O)-1:
O[random.randint( 0, i-1)] += C[i]
else:
O[i+1] += C[i]
assert sum(O) == M
assert len(O) == N

Regards,
Jordan

[Paul Rubin]

Re: number generator

"MonkeeSage " <MonkeeSage@gma il.comwrites:

Taking your comment and running with it...this is pretty much
cheating, and requires that M be evenly divisible by N, and only works
well with smaller N values, and selections are limited to numbers in
the 1 to (M/N)+(M/N) range...but hey; other than that it's perfect, heh.

This still doesn't make terribly much sense in terms of the distribution
you get.

The fencepost method still seems to be simplest:

t = sorted(random.s ample(xrange(1, 50), 4))
print [(j-i) for i,j in zip([0]+t, t+[50])]

[MonkeeSage]

Re: number generator

On Mar 10, 6:47 pm, Paul Rubin <http://phr...@NOSPAM.i nvalidwrote:

The fencepost method still seems to be simplest:
>
t = sorted(random.s ample(xrange(1, 50), 4))
print [(j-i) for i,j in zip([0]+t, t+[50])]

Simpler, true, but I don't think it gives any better distribution...

import random
def cheat(n, m):
N, M = n, m
D = M/N
O = [D] * N
C = []
for i in O:
C.append(random .randint(1, D-1))
for i in range(0, len(O), 2):
O[i] -= C[i]
if i == len(O)-1:
O[random.randint( 0, i-1)] += C[i]
else:
O[i+1] += C[i]
print 'CHEAT:'
print O

def fence(n, m):
t = sorted(random.s ample(xrange(1, m), n-1))
print 'FENCE:'
print [(j-i) for i,j in zip([0]+t, t+[m])]

for i in range(10):
print 'Run: %d:' % (i+1)
cheat(10, 80)
fence(10, 80)
print

Output:

Run: 1:
CHEAT:
[1, 15, 1, 15, 5, 11, 5, 11, 1, 15]
FENCE:
[4, 9, 24, 7, 3, 9, 11, 7, 3, 3]

Run: 2:
CHEAT:
[1, 15, 5, 11, 5, 11, 1, 15, 7, 9]
FENCE:
[15, 12, 13, 7, 1, 4, 5, 6, 4, 13]

Run: 3:
CHEAT:
[1, 15, 3, 13, 3, 13, 2, 14, 7, 9]
FENCE:
[2, 9, 12, 15, 4, 5, 2, 3, 19, 9]

Run: 4:
CHEAT:
[7, 9, 2, 14, 5, 11, 4, 12, 3, 13]
FENCE:
[2, 2, 4, 7, 1, 11, 15, 13, 6, 19]

Run: 5:
CHEAT:
[5, 11, 3, 13, 5, 11, 7, 9, 4, 12]
FENCE:
[2, 4, 11, 10, 13, 16, 2, 18, 1, 3]

Run: 6:
CHEAT:
[5, 11, 3, 13, 2, 14, 6, 10, 1, 15]
FENCE:
[1, 4, 13, 5, 2, 26, 5, 4, 16, 4]

Run: 7:
CHEAT:
[4, 12, 4, 12, 4, 12, 4, 12, 5, 11]
FENCE:
[8, 3, 5, 15, 8, 15, 2, 3, 10, 11]

Run: 8:
CHEAT:
[3, 13, 5, 11, 6, 10, 1, 15, 2, 14]
FENCE:
[25, 15, 2, 5, 2, 10, 6, 1, 9, 5]

Run: 9:
CHEAT:
[6, 10, 3, 13, 2, 14, 1, 15, 5, 11]
FENCE:
[11, 9, 3, 3, 7, 4, 8, 28, 1, 6]

Run: 10:
CHEAT:
[2, 14, 3, 13, 6, 10, 2, 14, 2, 14]
FENCE:
[12, 5, 23, 2, 3, 4, 4, 11, 5, 11]

Granted, I'm just eyeballing it, but they look fairly equal in terms
of distribution.

Regards,
Jordan

[Paulo da Silva]

Re: number generator

Paul Rubin escreveu:

Paulo da Silva <psdasilvaX@eso tericaX.ptXwrit es:

>May be this is what you want ...
>I didn't test it enough ... but seems fine.

>
That's way too complicated. Think about Gerald Flanagan's description
of the telegraph poles, and how to implement simply. It is a two liner.

I hadn't seen that yet. A *nice idea*. Just two lines!!!

I had a similar problem but with floats (%). I solved it using
the previous way in C. For float it is very simple. So I
adapted it for python and ints. That resulted in a lot more
complex code.