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. -- http://mail.python.org/mailman/listinfo/python-list