number generator

[Terry Reedy]

Re: number generator


"Anton Vredegoor" <anton.vredegoo r@gmail.comwrot e in message
news:esvepk$1cu $1@news3.zwoll1 .ov.home.nl...
| 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

If any of the 1s appear at the ends or together, then you would have 0s in
the partition, which is not allowed, as I understood the spec.

| unique permutations) which are a lot simpler to compute than partitions.

I think the simplicity is actually about the same.

Terry Jan Reedy

[Anton Vredegoor]

Re: number generator

Terry Reedy wrote:

"Anton Vredegoor" <anton.vredegoo r@gmail.comwrot e in message
| 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
>
If any of the 1s appear at the ends or together, then you would have 0s in
the partition, which is not allowed, as I understood the spec.

Yes, I was writing about the bricks and bins problem from 4 years ago
which is very similar.

| unique permutations) which are a lot simpler to compute than partitions.
>
I think the simplicity is actually about the same.

Probably yes. It's like the difference between Pascal's triangle and the
partition numbers' triangle. Anyway, Paul Rubin's idea in this same
thread stimulated me to simplify my code a lot. It's rather late here so
I hope I haven't slipped up again.

def comb(i,n,k):
for j in range(k,0,-1):
while noverk(n,j) i :
n -= 1
i -= noverk(n,j)
yield n

def noverk(n,k):
return reduce(lambda a,b: a*(n-b)/(b+1),range(k), 1)

def bb(i,bricks,bin s):
L = [j+1 for j in comb(i,bricks,b ins-1)]
return [(i-j) for i,j in zip([bricks]+L,L+[0])]

def test():
bricks, bins = 6,4
n = noverk(bricks-1,bins-1)
for i in range(n):
print bb(i,bricks,bin s)

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

A.

[shellux]

Re: number generator

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

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

import random

def genRandList(n,l eft):
L = []
if n left:
return L

while n:
L.append(int(ra ndom.random()*( left-n+1))+1)
n -= 1;
left -= L[-1]

return L

[Steven D'Aprano]

Re: number generator

On Sat, 10 Mar 2007 16:02:56 -0800, Paul Rubin wrote:

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?

Oh! You know that bit where I said that every imaginable sequence of
integers was random? I take it back.

Oh wait. I never said anything of the sort. Not every sequence of ints is
a random sequence.

Although... your question is deeper than it appears at first glance. In
any truly random sequence, you should expect to find repeated values. If
you wait long enough, you should get a sequence of 3,3,3... for any number
of threes you like. (Or, naturally, any other integer.) If you wait long
enough, you should get a billion threes.



--
Steven.

[Steven D'Aprano]

Re: number generator

On Sat, 10 Mar 2007 17:19:38 -0800, MonkeeSage wrote:

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

[snip]

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

It's easy enough to see whether the fencepost method gives a uniform
distribution.


def fence(n, m):
t = [0] + sorted(random.s ample(xrange(1, m), n-1)) + [m]
L = [(j-i) for i,j in zip(t[:-1], t[1:])]
assert sum(L) == m
assert len(L) == n
return L


def collate(count, n, m):
bins = {}
for _ in xrange(count):
L = fence(n, m)
for x in L:
bins[x] = 1 + bins.get(x, 0)
return bins


collate(1000, 10, 80)

gives me the following sample:

{1: 1148, 2: 1070, 3: 869, 4: 822, 5: 712,
6: 633, 7: 589, 8: 514, 9: 471,
10: 406, 11: 335, 12: 305, 13: 308, 14: 242,
15: 232, 16: 190, 17: 172, 18: 132, 19: 132,
20: 124, 21: 87, 22: 91, 23: 72, 24: 50,
25: 48, 26: 45, 27: 33, 28: 29, 29: 22,
30: 19, 31: 20, 32: 12, 33: 12, 34: 11,
35: 11, 36: 5, 37: 9, 38: 2, 39: 4, 40: 5,
42: 1, 43: 3, 45: 2, 49: 1}

Clearly the distribution isn't remotely close to uniform.

To compare to the "cheat" method, calculate the mean and standard
deviation of this sample, and compare to those from the other method.
(Code left as an exercise for the reader.) When I do that, I get a mean
and standard deviation of 8 and 6.74 for the fencepost method, and 8 and
4.5 for the "cheat" method. That implies they are different distributions.



--
Steven.

[MonkeeSage]

Re: number generator

On Mar 10, 11:26 pm, Steven D'Aprano
<s...@REMOVE.TH IS.cybersource. com.auwrote:

To compare to the "cheat" method, calculate the mean and standard
deviation of this sample, and compare to those from the other method.

I belieive you (mainly because I'm too lazy to write the sieve,
hehe). ;)

Regards,
Jordan

[greg]

Re: number generator

MonkeeSage wrote:

this ... requires that M be evenly divisible by N,

No, it doesn't -- I never said the numbers had
to be *equal*.

and only works well with smaller N values,

Why?

and selections are limited to numbers in the
1 to (M/N)+(M/N) range

I don't understand what you mean by that. Note
that the adjustments don't have to be restricted
to *adjacent* numbers -- you can pick any pair
of numbers and transfer an amount from one to
the other, as long as neither of them goes
below 1, and you can perform as many adjustments
as you like. So *any* sequence of numbers that
sums to M is a possible output from some
algorithm of this kind.

As for the distribution, the OP said there were
"no other restrictions", so it seems that the
distribution doesn't matter. Actually, if you
take that at face value, the numbers don't
even have to be *random* at all... or,
equivalently, they can have a very skewed
distribution. :-)

--
Greg

[MonkeeSage]

Re: number generator

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

MonkeeSage wrote:

this ... requires that M be evenly divisible by N,

>
No, it doesn't -- I never said the numbers had
to be *equal*.

Sorry for not being clear. I was refering to my specific
implementation of the algorithm, not the generic design pattern.

Regards,
Jordan

[Army1987]

Re: number generator


"cesco" <fd.calabrese@g mail.comha scritto nel messaggio
news:1173451441 .077648.321270@ c51g2000cwc.goo glegroups.com.. .

>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

You can initialize a list to [1, 1, 1, 1, 1], and generate 45 random
integers between 1 and 5, and every time a number is generated, increase the
Nth number in the list by one.

Not all distinct lists will have the same chance of occurring, e.g. [46, 1,
1, 1, 1] will be much less likely than [10, 10, 10, 10, 10]. Depending on
what you need these numbers for, it can be a good thing or a bad thing.

--Army1987

[Alex Martelli]

Re: number generator

Army1987 <please.ask@for .itwrote:

"cesco" <fd.calabrese@g mail.comha scritto nel messaggio
news:1173451441 .077648.321270@ c51g2000cwc.goo glegroups.com.. .

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

>
>
You can initialize a list to [1, 1, 1, 1, 1], and generate 45 random
integers between 1 and 5, and every time a number is generated, increase the
Nth number in the list by one.
>
Not all distinct lists will have the same chance of occurring, e.g. [46, 1,
1, 1, 1] will be much less likely than [10, 10, 10, 10, 10]. Depending on
what you need these numbers for, it can be a good thing or a bad thing.

And a1-liner way to get the numbers (net of the mandatory +1 for each)
is:

map([random.randrang e(5) for i in xrange(45)].count, xrange(5))

i.e., this gives 5 integers (each between 0 and 45 included) summing to
45 -- add 1 to each of them to get the desired result.

Without any specification regarding the distributions required for the
"5 random numbers" it's really impossible to say whether these are
better or worse than other proposed solutions.


Alex

[Duncan Booth]

Re: number generator

aleax@mac.com (Alex Martelli) wrote:

Without any specification regarding the distributions required for the
"5 random numbers" it's really impossible to say whether these are
better or worse than other proposed solutions.

FWIW, I decided it would be fun to see what kind of implementation I
could come up test driven and avoiding reading the thread or background
references too much first. So starting from:

import unittest

def partition(total , n, min):
return [50]

class PartitionTests( unittest.TestCa se):
def testsinglevalue (self):
self.assertEqua l([50], partition(50, 1, 1))

if __name__=='__ma in__':
unittest.main()

I eventually worked my way through 15 revisions to the code below.

The tests were added in the order you see them below. The commented out
function is the one I had arrived at before I added the first
distribution test which triggered a major refactor (although the code
ended up remarkably similar): if you uncomment it all but the
distribution tests pass.

I don't really like the arbitrary limits for the distribution tests, but
I'm not sure how else to test that sort of thing. And as Alex said,
without knowing what distribution the OP wanted the definition I chose
to use is completely arbitrary.

----- partition.py -------
import unittest, collections
from random import randint, sample

def partition(total , n, min):
maxtotal = total - n*(min-1)
posts = sorted(sample(x range(1, maxtotal), n-1))
return [ (b-a)+min-1 for (a,b) in zip([0]+posts, posts+[maxtotal]) ]

# def partition(total , n, min):
# maxtotal = total - (n*min)
# sums = sorted(randint( 0, maxtotal) for i in range(n-1))
# return [(b-a)+min for (a,b) in zip([0]+sums, sums+[maxtotal])]

class PartitionTests( unittest.TestCa se):
def testsinglevalue (self):
self.assertEqua l([50], partition(50, 1, 1))

def testnvalues(sel f):
self.assertEqua l([1]*5, partition(5, 5, 1))

def testnminusone(s elf):
self.assertEqua l([1]*4+[2], sorted(partitio n(6, 5, 1)))

def testnminusone2( self):
# Check we get all possible results eventually
expected = set([(1,1,2), (1,2,1), (2,1,1)])
for i in range(100):
got = tuple(partition (4,3,1))
if got in expected:
expected.remove (got)
if not len(expected):
break
self.assertEqua l(len(expected) , 0)

def testdistributio n(self):
# Make sure we get each of 3 possible outcomes roughly
# equally often.
actual = collections.def aultdict(int)
for i in range(1000):
actual[tuple(partition (4,3,1))] += 1
counts = actual.values()
assert (min(counts) 250)
assert (max(counts) < 400)

def testdistributio n2(self):
# More arbitrary limits for the distribution. 10 possible
# outcomes this time.
actual = collections.def aultdict(int)
ntries = 10000
for i in range(ntries):
actual[tuple(partition (6,3,1))] += 1
counts = actual.values()
assert (min(counts) 900)
assert (max(counts) < 1100)

def testmintwo(self ):
self.assertEqua l([2]*50, partition(100,5 0,2))

def testminzero(sel f):
self.assertEqua l([0]*20, partition(0,20, 0))

def testcantdoit(se lf):
self.assertRais es(ValueError, partition, 100, 51, 2)

if __name__=='__ma in__':
unittest.main()

--------------------------

[Nick Craig-Wood]

Re: number generator

Paul Rubin <httpwrote:

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

Mmm, nice.

Here is another effort which is easier to reason about the
distribution produced but not as efficient.

def real(N, M):
while 1:
t = [ random.random() for i in range(N) ]
factor = M / sum(t)
t = [ int(round(x * factor)) for x in t]
if sum(t) == M:
break
print "again"
assert len(t) == N
assert sum(t) == M
return t

It goes round the while loop on average 0.5 times.

If 0 isn't required then just test for it and go around the loop again
if found. That of course skews the distribution in difficult to
calculate ways!

--
Nick Craig-Wood <nick@craig-wood.com-- http://www.craig-wood.com/nick

[Carsten Haese]

Re: number generator

On Sat, 2007-03-10 at 22:27 -0500, Terry Reedy wrote:

"Anton Vredegoor" <anton.vredegoo r@gmail.comwrot e in message
news:esvepk$1cu $1@news3.zwoll1 .ov.home.nl...
| 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 [...]
| [...] 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
>
If any of the 1s appear at the ends or together, then you would have 0s in
the partition, which is not allowed, as I understood the spec.

Correct, the OP's spec doesn't allow 0s, but the problem can be easily
transformed back and forth between positive partitions and non-negative
partitions. In order to partition M into N positive numbers, partition
(M-N) into N non-negative numbers and increase each part by 1.

There must be some other constraint on what P(M,N) means, or I just
solved a 300 year old problem.

-Carsten

[Hendrik van Rooyen]

Re: number generator

"Nick Craig-Wood" <nick@craig-wood.comwrote:

Paul Rubin <httpwrote:

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

>
Mmm, nice.
>
Here is another effort which is easier to reason about the
distribution produced but not as efficient.
>
def real(N, M):
while 1:
t = [ random.random() for i in range(N) ]
factor = M / sum(t)
t = [ int(round(x * factor)) for x in t]
if sum(t) == M:
break
print "again"
assert len(t) == N
assert sum(t) == M
return t
>
It goes round the while loop on average 0.5 times.
>
If 0 isn't required then just test for it and go around the loop again
if found. That of course skews the distribution in difficult to
calculate ways!
>

I have been wondering about the following as this thread unrolled:

Is it possible to devise a test that can distinguish between sets
of:

- five random numbers that add to 50, and
- four random numbers and a fudge number that add to 50?

My stats are way too small and rusty to attempt to answer
the question, but it seems intuitively a very difficult thing.

- Hendrik

[Dick Moores]

Re: number generator

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