An Algorithm For Randomly Generating Integer Partitions Of A Particular Length, In Python?

I've been using the random_element() function provided by SAGE to generate random integer partitions for a given integer (N) that are a particular length (S). I'm trying to generat

Solution 1:

Finally, I have a definitively unbiased method that has a zero rejection rate. Of course, I've tested it to make sure the results are representative samples of entire feasible sets. It's very fast and totally unbiased. Enjoy.

from sage.allimport *
import random

First, a function to find the smallest maximum addend for a partition of n with s parts

defmin_max(n,s):

    _min = int(floor(float(n)/float(s)))
    ifint(n%s) > 0:
        _min +=1return _min

Next, A function that uses a cache and memoiziation to find the number of partitions of n with s parts having x as the largest part. This is fast, but I think there's a more elegant solution to be had. e.g., Often: P(N,S,max=K) = P(N-K,S-1) Thanks to ante (https://stackoverflow.com/users/494076/ante) for helping me with this: Finding the number of integer partitions given a total, a number of parts, and a maximum summand

D = {}
def P(n,s,x):
    if n > s*x or x <= 0: return0ifn== s*x: return1if (n,s,x) not in D:
        D[(n,s,x)] = sum(P(n-i*x, s-i, x-1) for i in xrange(s))
    return D[(n,s,x)]

Finally, a function to find uniform random partitions of n with s parts, with no rejection rate! Each randomly chosen number codes for a specific partition of n having s parts.

defrandom_partition(n,s):
    S = s
    partition = []
    _min = min_max(n,S)
    _max = n-S+1

    total = number_of_partitions(n,S)
    which = random.randrange(1,total+1) # random numberwhile n:
        for k inrange(_min,_max+1):
            count = P(n,S,k)
            if count >= which:
                count = P(n,S,k-1)
                break

        partition.append(k)
        n -= k
        if n == 0: break
        S -= 1
        which -= count
        _min = min_max(n,S)
        _max = k

    return partition

Solution 2:

I ran into a similar problem when I was trying to calculate the probability of the strong birthday problem.

First off, the partition function explodes when given only modest amount of numbers. You'll be returning a LOT of information. No matter which method you're using N = 10000 and S = 300 will generate ridiculous amounts of data. It will be slow. Chances are any pure python implementation you use will be equally slow or slower. Look to making a CModule.

If you want to try python the approach I took as a combination of itertools and generators to keep memory usage down. I don't seem to have my code handy anymore, but here's a good impementation:

http://wordaligned.org/articles/partitioning-with-python

EDIT:

Found my code:

defpartition(a, b=-1, limit=365):
  if (b == -1):
    b = a
  if (a == 2or a == 3):
    if (b >= a and limit):
      yield [a]
    else:
      returnelif (a > 3):
    if (a <= b):
      yield [a]
    c = 0if b > a-2:
      c = a-2else:
      c = b
    for i in xrange(c, 1, -1):
      if (limit):
        for j in partition(a-i, i, limit-1):
          yield [i] + j

Solution 3:

Simple approach: randomly assign the integers:

def random_partition(n, s):
    partition = [0] * s
    for x in range(n):
        partition[random.randrange(s)] +=1return partition