M
Mel Wilson
That's a good one! Three-liner.Gerard said:
Cheers, Mel.
Cheers, Mel.
P
Paulo da Silva
cesco escreveu:
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(lambda x: xl[x]>1,range(m))
shuffle(ixs)
for i in ixs[:s-n]: xl-=1
else:
ixs=range(m)
shuffle(ixs)
for i in ixs[:n-s]: xl+=1
return xl
# Test it ...
xl=GenRInt(10,50)
print xl,"->",sum(xl)
print
xl=GenRInt(100,10000)
print xl,"->",sum(xl)
print
xl=GenRInt(1000,1000)
print xl,"->",sum(xl)
Regards.
Paulo
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(lambda x: xl[x]>1,range(m))
shuffle(ixs)
for i in ixs[:s-n]: xl-=1
else:
ixs=range(m)
shuffle(ixs)
for i in ixs[:n-s]: xl+=1
return xl
# Test it ...
xl=GenRInt(10,50)
print xl,"->",sum(xl)
xl=GenRInt(100,10000)
print xl,"->",sum(xl)
xl=GenRInt(1000,1000)
print xl,"->",sum(xl)
Regards.
Paulo
P
Paul Rubin
Paulo da Silva said:
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.
T
Terry Reedy
| 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
|
| > 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
A
Anton Vredegoor
Terry said:
Yes that was one of my first ideas too. But later on Steven pointed out
that one can view the problem like this:
00010000100010100
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) for i in R]
for i in R: np = np*(n-i)/(bf+1)
return [(i,np*L[i:].count(L)/n) for i in R if not bf]
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 = 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,bins):
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,bins)
if __name__=='__main__':
test()
Great book!
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.
S
Steven D'Aprano
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.
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.expovariate) and the famous bell curve
distribution (random.normalvariate).
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.
A
Anton Vredegoor
Anton said:
replace these lines in the code by:
L = [1] * (bins-1) + [0] * (bricks-bins)
A.
P
Paul Rubin
Steven D'Aprano said:
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.
M
MonkeeSage
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 -= C
if i == len(O)-1:
O[random.randint(0, i-1)] += C
else:
O[i+1] += C
assert sum(O) == M
assert len(O) == N
Regards,
Jordan
P
Paul Rubin
MonkeeSage said:
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.sample(xrange(1,50), 4))
print [(j-i) for i,j in zip([0]+t, t+[50])]
M
MonkeeSage
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 -= C
if i == len(O)-1:
O[random.randint(0, i-1)] += C
else:
O[i+1] += C
print 'CHEAT:'
print O
def fence(n, m):
t = sorted(random.sample(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)
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
P
Paulo da Silva
Paul Rubin escreveu:
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.
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.
T
Terry Reedy
| 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:
|
| 00010000100010100
|
| 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
|
| > 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:
|
| 00010000100010100
|
| 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
A
Anton Vredegoor
Terry said:
Yes, I was writing about the bricks and bins problem from 4 years ago
which is very similar.
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,bins):
L = [j+1 for j in comb(i,bricks,bins-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,bins)
if __name__=='__main__':
test()
A.
S
shellux
import random
def genRandList(n,left):
L = []
if n > left:
return L
while n:
L.append(int(random.random()*(left-n+1))+1)
n -= 1;
left -= L[-1]
return L
S
Steven D'Aprano
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.
S
Steven D'Aprano
It's easy enough to see whether the fencepost method gives a uniform
distribution.
def fence(n, m):
t = [0] + sorted(random.sample(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.
M
MonkeeSage
I belieive you (mainly because I'm too lazy to write the sieve,
hehe).
Regards,
Jordan
G
greg
MonkeeSage said:
No, it doesn't -- I never said the numbers had
to be *equal*.
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.
M
MonkeeSage
Sorry for not being clear. I was refering to my specific
implementation of the algorithm, not the generic design pattern.
Regards,
Jordan