number generator
Anton Vredegoor
anton.vredegoor at gmail.com
Tue Mar 13 14:59:23 CET 2007
Dick Moores wrote:
> If the added constraint is instead that the probability of generating
> a given list of length N be the same as that of generating any other
> list of length N, then I believe my function does the job. Of course,
> [1,46,1,1,1] and [1,1,46,1,1], as Python lists, are distinct. I ran
> this test for M == 8 and N == 4:
Yes, I believe your function is OK. But the 'fencepost' method posted
earlier in this thread also does this and it's faster AND it's only two
line of code ...
> A = []
> B = []
> for x in range(100000):
> lst = sumRndInt(8,4)
> if lst not in A:
> A.append(lst)
> B.append(1)
> else:
> i = A.index(lst)
> B[i] += 1
>
> A.sort()
Doesn't sorting break the correspondence between A and B? Also, a more
pythonic way to count would be to convert the lst into a tuple and then
do something with a dictionary. Dictionaries have faster lookup. For
example:
T = tuple(lst)
D[T] = D.get(T,0) + 1
in the loop in order to count the occurrences.
I'm totally fascinated with this stuff myself so it's a bit hard to
guess whether someone still is interested, but anyway, here are some
further explorations involving partitions. The code prints the number of
distinct permutations for each partition.
from operator import mul
def part(m,n,r):
L = [0]*n
while m:
x = pn(m-1,n-1)
if r < x:
L[n-1] += 1
m -= 1
n -= 1
else:
for i in range(n):
L[i] += 1
r -= x
m -= n
return L
def memoize(fn):
cache = {}
def proxy(*args):
try: return cache[args]
except KeyError: return cache.setdefault(args, fn(*args))
return proxy
@memoize
def pn(m,n):
if m<n or n==0:
return 0
if m==n or n==1:
return 1
return pn(m-1,n-1)+pn(m-n,n)
@memoize
def fac(n):
if n == 1:
return 1
return n*fac(n-1)
@memoize
def ncomb(n,k):
return reduce(lambda a,b: a*(n-b)/(b+1),range(k),1)
@memoize
def _np(T):
if T:
up = fac(sum(T))
down = reduce(mul,map(fac,T))
return up/down
else:
return 1
def nperm(L):
f = dict((x,L.count(x)) for x in set(L))
return _np(tuple(f.values()))
def test():
m = 50
n = 5
np=pn(m,n)
total = 0
for r in xrange(np):
x = part(m,n,r)
np = nperm(x)
total += np
print np,x
assert total == ncomb(m-1,n-1)
if __name__=='__main__':
test()
I posted some easy way of generating all outcomes by index -using a
combinations function- before in this thread. Using just a single
randint call one could output a random list of numbers adding up to
something.
But I think it would be possible to do it with distinct permutations of
these partitions too. I think I did that in old thread. The only problem
is that in order to look up which distinct permutation of which
partition is indexed there should be a way to compute a table containing
info about how many permutations a certain partition contributes to the
total. But the code would then also need a distinct permutation by index
function (I've got one but it's not exactly beautiful) while the code is
becoming very complex even now without the extra lookup table, compared
to the simple combinations code.
And compared to the two line fencepost method it's just crazy :-)
But I have a hunch there must be a way to generate such a table without
actually computing any partitions at all and then one could do some kind
of 3d bisect to look things up. Maybe in a few years, or sooner if
someone posts an idea that simplifies things.
A.
More information about the Python-list
mailing list