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.)
2. 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]
3. 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.
4. 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 a revised function that implements the new algorithm:
def random_ints_with_sum(n):
"""
Generate positive random integers summing to `n`, sampled
uniformly from the ordered integer partitions of `n`.
"""
p = 0
for _ in xrange(n - 1):
p += 1
if random.randrange(2):
yield p
p = 0
yield p + 1
And here's an example distribution after a million calls to the revised function:
Partition Count
----------- ------
4, 125042
3, 1 124848
2, 2 125189
2, 1, 1 125126
1, 3 124861
1, 2, 1 125152
1, 1, 2 124248
1, 1, 1, 1 125534
You'll see that this is very close to uniform.
Again, I should emphasize that since I don't know what your function is going to be used for, I don't know whether changing it so that it samples uniformly from the ordered integer partitions is the right thing to do. But if it is, now you know how to do it.
(Who would have thought there would be so much to write about a six-line function?)
5. Chinese restaurant process
You updated your question to say that you are trying to simulate a Chinese restaurant process. I have to say that I can't relate the code in your question to this process, which has nothing to do with numbers that sum to a particular total. So I'm puzzled! Maybe you can say more about how the code you posted relates to this process?
Anyway, if you want to generate a sample from this distribution, the easiest thing to do is to simulate the process directly:
def chinese_restaurant_partition(n):
"""
Return a random partition of the numbers from 1 to n generated by
the Chinese restaurant process.
"""
partition = [] # list of sets
assignment = [] # set each number is assigned to
for i in xrange(n):
r = random.randrange(i + 1)
if r < i:
# assign i + 1 to existing block
block = assignment[r]
else:
# create new block
block = set()
partition.append(block)
block.add(i + 1)
assignment.append(block)
return partition
For example:
>>> chinese_restaurant_partition(4)
[set([1]), set([2, 4]), set([3])]
This distribution looks like this (again, after generating a million samples):
Partition Count
---------- ------
1234 249231
134, 2 83453
124, 3 82664
123, 4 83569
1, 234 83161
14, 23 42126
13, 24 41688
12, 34 41726
14, 2, 3 41891
13, 2, 4 41569
12, 3, 4 42022
1, 24, 3 41522
1, 23, 4 41719
1, 2, 34 41867
1, 2, 3, 4 41792
