number generator

[Steven D'Aprano]

Re: number generator

On Wed, 14 Mar 2007 19:25:46 +1100, Steven D'Aprano wrote:

Now that I've seen your _partition() function, I'm quite impressed. It is
still brute-force, but it avoids generating all 50**5 non-unique lists. By
my count, it only has to throw away 11,294 lists to generate the 2611
unique lists it returns.

Ignore that count. I don't know where I got 11,294 from, the correct
figure is 10,358.

Oh, I seem to have found a bug in the _partitions() function. I believe it
is missing some of the partitions.

>>list(_partiti ons(25, 24))

[(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2)]

>>list(_partiti ons(25, 25))

[]


--
Steven D'Aprano

[Raymond Hettinger]

Re: number generator

To make the solutions equi-probable, a simple approach is to

recursively enumerate all possibilities and then choose one of them
with random.choice() .

Since people are posting their solutions now (originally only hints
were provided for the homework problem), here's mine:

def genpool(n, m):
if n == 1:
yield [m]
else:
for i in xrange(1, m):
for rest in genpool(n-1, m-i):
yield rest + [i]

import random
print random.choice(l ist(genpool(n=4 , m=20)))

[Raymond Hettinger]

Re: number generator

[Alex Martelli]

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.

This is a really nice approach. Besides being fast, it is not too
hard to see that it is correct.

FWIW, here's a variant with a count using the new defaultdict:

n, m = 5, 45
bag = collections.def aultdict(int)
for i in xrange(m):
bag[random.randrang e(n)] += 1
ans = [bag[k] for k in range(n)]

[Anton Vredegoor]

Re: number generator

Raymond Hettinger wrote:

Since people are posting their solutions now (originally only hints
were provided for the homework problem), here's mine:

Homework problem? Do you have some information from the OP that I can't
find in this thread? Anyway, I consider the 'homework' idea and the
associated self concept that turns people into -for example-
backstabbing computer scientists who never release their code as the
root of all evil in the educational system. Why should I uphold a moral
code that I don't agree with? To me people posting homework problems are
like refugees which I will help if I can.

def genpool(n, m):
if n == 1:
yield [m]
else:
for i in xrange(1, m):
for rest in genpool(n-1, m-i):
yield rest + [i]
>
import random
print random.choice(l ist(genpool(n=4 , m=20)))

OK back to the *computer* code. Great function! And it's ideally suited
for memoization too. Too bad this memoizor doesn't accept keyword
arguments, but for the rest it works fine and greatly speeds it up.

import random

def memoize(fn):
cache = {}
def proxy(*args):
try: return cache[args]
except KeyError: return cache.setdefaul t(args, fn(*args))
return proxy

@memoize
def genpool(n, m):
if n == 1:
yield [m]
else:
for i in xrange(1, m):
for rest in genpool(n-1, m-i):
yield rest + [i]

def test():
print random.choice(l ist(genpool(5,5 0)))

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

A.

[cesco]

Re: number generator

Since people are posting their solutions now (originally only hints

were provided for the homework problem), here's mine:

Well, I never really said it was a homework problem. Sure there are
more implications to my question that I had first imagined and I'm
really happy I could get so many insights but the question did
originate from a real problem I was facing in my research.

Thanks to everyone for the wonderful thread so far
Francesco

[Duncan Smith]

Re: number generator

Duncan Smith wrote:

greg wrote:
>

>>Gabriel Genellina wrote:
>>
>>

>>>The 5th number is not "random".

>>
>>
>>More precisely, the fifth number is not *independent*
>>of the others. You can't have five independent random
>>numbers that sum to 50; only four independent numbers
>>plus a dependent one.
>>
>>--
>>Greg

>
>
In the interests of precision, that should probably read "are
constrained to sum to 50"; it's quite possible to generate a sequence of
independent random variates that just happen to sum to 50 (as I'm sure
you know).
>
A fairly efficient way of generating random multinomial variates (which
would satisfy the OP's problem)

[snip]

That is, the OP's original problem (without the positivity constraint
added in a later post).

Duncan

[Alex Martelli]

Re: number generator

Raymond Hettinger <python@rcn.com wrote:

[Alex Martelli]

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.

>
This is a really nice approach. Besides being fast, it is not too
hard to see that it is correct.
>
FWIW, here's a variant with a count using the new defaultdict:
>
n, m = 5, 45
bag = collections.def aultdict(int)
for i in xrange(m):
bag[random.randrang e(n)] += 1
ans = [bag[k] for k in range(n)]

Neat -- and you can use 1+bag[k] in the LC to adjust the results if
needed, of course.


Alex

[Duncan Smith]

Re: number generator

Hendrik van Rooyen wrote:

"Duncan Smith" <bu...ard@urubu .freeserve.co.u kwrote:
>
>
>

>>Yes, if the generating processes yield numbers from different
>>probability mass functions. You could simply look at the likelihood
>>ratio. Otherwise, the likelihood ratio will be 1.
>>

>
I was thinking about the same random number generator being used in the two
disparate ways.
>
- Hendrik
>

The code I posted for multinomial variates repeatedly generates
independent Poissons until the total is less than, or equal to, the
desired total. Then the total is made up by repeatedly sampling from a
discrete distribution (multinomial with n==1). If you replace the
second stage by just increasing a single count by the necessary amount,
then the two mass functions are clearly different. I'm not sure that
I'd count this as two approaches using "the same random number generator".

Duncan

[Shane Geiger]

Re: number generator

Raymond: It looks to me as if you are trying to turn a generator into
a list in the final line. That doesn't work.



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

>
Since people are posting their solutions now (originally only hints
were provided for the homework problem), here's mine:
>
def genpool(n, m):
if n == 1:
yield [m]
else:
for i in xrange(1, m):
for rest in genpool(n-1, m-i):
yield rest + [i]
>
import random
print random.choice(l ist(genpool(n=4 , m=20)))
>
>

--
Shane Geiger
IT Director
National Council on Economic Education
sgeiger@ncee.ne t | 402-438-8958 | http://www.ncee.net

Leading the Campaign for Economic and Financial Literacy

[Paul Rubin]

Re: number generator

Steven D'Aprano <steve@REMOVEME .cybersource.co m.auwrites:

If you generate all the possible sets of five numbers between 1 and 50,
there are 50**5 of them, not 2611.

Yes, the idea is generate only the sets that add up to 50.

unique_partitio ns(60, 6) takes 0.8 seconds; unique_partitio ns(80, 8)
takes about 25 seconds; unique_partitio ns(80, 10) takes about 80 seconds,
and unique_partitio ns(81, 10) takes over 90 seconds.

Hmm, interesting. Maybe some more optimization is possible.

(E.g. unique_partitio ns(80, 10) returns 533,975 unique lists.
_partitions(80, 10) gives 3,233,568 non-unique lists.)

Well that's just 6x "inflation" due to duplicates, so I dunno what
else can be done for exhaustive enumeration. Maybe another approach
to generating the k'th partition is possible. I'll try to think about
this.

[Paul Rubin]

Re: number generator

"Raymond Hettinger" <python@rcn.com writes:

Since people are posting their solutions now (originally only hints
were provided for the homework problem), here's mine:
>
def genpool(n, m):
if n == 1:
yield [m]
else:
for i in xrange(1, m):
for rest in genpool(n-1, m-i):
yield rest + [i]
>
import random
print random.choice(l ist(genpool(n=4 , m=20)))

This generates a lot of the partitions more than once, with
possibly unequal probability.

[Anton Vredegoor]

Re: number generator

Paul Rubin wrote:

>def genpool(n, m):
> if n == 1:
> yield [m]
> else:
> for i in xrange(1, m):
> for rest in genpool(n-1, m-i):
> yield rest + [i]
>>
>import random
>print random.choice(l ist(genpool(n=4 , m=20)))

>
This generates a lot of the partitions more than once, with
possibly unequal probability.

Well, I just noticed that with my memoization function it produces too
little :-(

But I hope you notice that this function doesn't create only partitions
but all possible outcomes?

A.

[Paul Rubin]

Re: number generator

Steven D'Aprano <steve@REMOVEME .cybersource.co m.auwrites:

>list(_partitio ns(25, 24))

[(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2)]

>list(_partitio ns(25, 25))

[]

Hmm. I'll look into this later if I get a chance. Thanks.

[Anton Vredegoor]

Re: number generator

Anton Vredegoor wrote:

def memoize(fn):
cache = {}
def proxy(*args):
try: return cache[args]
except KeyError: return cache.setdefaul t(args, fn(*args))
return proxy

Sorry this doesn't work in this case. This works:

def memoize(fn):
cache = {}
def proxy(*args):
try: return cache[args]
except KeyError: return cache.setdefaul t(args, list(fn(*args)) )
return proxy

But then we lose all speed advantages from memoizing so
it's no good either.

A.