Generating random sequences while keeping sum fixed

The output is a random sequence, and the input is the sum of the sequence.

My solution is generating a random number rand_num from (0, sum_seq) at first, then draw another number randomly from (0, sum_seq - rand_num). By the way, all random numbers are integers.

import random

rand_list = [] # Random sequences buffer
def generater_random_list(num) :
    rand_num = random.randint(0, num)
    rand_list.append(rand_num)
    if num - rand_num == 0 :
        return 0
    else :
        return generater_random_list(num - rand_num)

It seems strange to create a buffer out of the function, so how can I improve it?

1. Comments on your code

-
The function stores its results in the global variable rand_list and always returns 0. This is a poor design of interface for two reasons. First, if you call generater_random_list twice, rand_list now contains the concatenation of the first and second lists:

>>> generater_random_list(10)
0
>>> rand_list
[2, 1, 5, 1, 0, 1]
>>> generater_random_list(10)
0
>>> rand_list
[2, 1, 5, 1, 0, 1, 9, 1]

(The caller could set rand_list = [] before the second call to generater_random_list, but it would be really annoying to have to keep remembering to do that.)

And second, what's the point of returning 0? That's no use to anyone. Python allows you just to write return as a shorthand for return None if you really have nothing worth returning, but here you do have something to return, namely the list of random numbers you just constructed.

-
There's no docstring. What does this function do and how do you call it?

-
You could choose a better name for the function than generater_random_list. (i) "Generator" is spelled with an "o". (ii) If you're going to name a function after its action, use the imperative form of the verb. (So use sort or multiply, rather than sorter or multiplier.) (iii) "Generator" has a specialized meaning in Python (referring to a generator), so best not to use it unless that's what you mean.

-
The Python style guide (PEP8) says, "Avoid extraneous whitespace immediately before a comma, semicolon, or colon."

-
When you're writing a function that produces a sequence of items, it's usually a good idea in Python to make it into a generator function that yields the items one by one (rather than a normal function that builds and returns a list of all the items). It's often convenient to process these items one by one, and a generator function allows you to do this without having to construct an intermediate list in memory. (And if you need a list, it's trivial to build one, by passing your generator to the function list.)

1. Revised code

def random_ints_with_sum(n):
    """
    Generate non-negative random integers summing to `n`.
    """
    while n > 0:
        r = random.randint(0, n)
        yield r
        n -= r

And here are some example calls:

>>> list(random_ints_with_sum(10))
[9, 1]
>>> list(random_ints_with_sum(10))
[10]
>>> list(random_ints_with_sum(10))
[0, 2, 8]

1. Comments on your design

-
Do you really mean to include 0 among the random integers? This suggests that you would be happy with

>>> list(random_ints_with_sum(1))
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]

and similar outputs. You don't say what you are using this function for, so I can't tell if this is right or wrong, but it looks well dodgy to me.

-
Even with 0 excluded, your implementation samples its range with a lot of bias. For example, the number 4 has eight ordered partitions into positive integers:

4   3, 1   2, 2   2, 1, 1   1, 3   1, 2, 1   1, 1, 2   1, 1, 1, 1

but your algorithm doesn't sample these partitions evenly. Here's a test program that calls random_ints_with_sum(4) a million times, and counts the number of times each result was generated:

>>> from collections import Counter
>>> Counter(tuple(random_ints_with_sum(4)) for _ in xrange(10 ** 6))

Here are the results:

Partition    Count
-----------  ------
4            249997
3, 1         250047
2, 2         124579
2, 1, 1      125113
1, 3          83425
1, 2, 1       83190
1, 1, 2       41875
1, 1, 1, 1    41774

If the partitions had been generated uniformly, each would have appeared about 125,000 times in the results. You can see that shorter partitions are generated more frequently, and longer partitions less frequently than in the uniform distribution.

Again, since you don't explain what your function is for, I can't tell whether this kind of bias is important or not.

1. Sampling partitions uniformly

Supposing that you wanted to sample the space of ordered integer partitions uniformly, how could you implement it?

First we have to know how to count ordered integer partitions. And to do that, there's a neat combinatorial observation. Consider a group of objects waiting to be partitioned:

If there are n objects, there are n − 1 locations where you could insert a partition (indicated by the dotted lines). For example, if we insert partitions at the first and the third locations, we get the partition 1, 2, 1:

Each subset of locations corresponds to a different ordered partition, and each ordered partition corresponds to a different subset of locations. This means that we can choose an ordered partition uniformly by choosing a subset of locations uniformly. There are 2n − 1 subsets of the n − 1 locations (for example, 4 objects have 23 = 8 ordered partitions, as noted above), and we can choose one of these subsets uniformly by putting each location into the subset with probability ½.

Here's

StackExchange Code Review Q#23728, answer score: 14