6
\$\begingroup\$

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?

\$\endgroup\$
11
\$\begingroup\$

1. Comments on your code

  1. 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.

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

  3. 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.

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

  5. 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

  1. 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.

  2. 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:

Four objects with three locations for partition

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:

Four objects partitioned as 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
\$\endgroup\$
1
\$\begingroup\$

Using a recursive approach -


from random import randint

def sequence(n):

   a = []

   def f(n):
      m = randint(1, n)
      if n > m:
         a.append(str(m))
         return f(n - m)
      else:
         a.append(str(n))
         return n

   f(n)
   return ' + '.join(a) + ' = %d' % n

Test code:

for i in xrange(10):
   print sequence(20)

Output:

7 + 11 + 2 = 20
14 + 4 + 1 + 1 = 20
5 + 10 + 3 + 2 = 20
1 + 17 + 1 + 1 = 20
1 + 5 + 13 + 1 = 20
3 + 12 + 2 + 3 = 20
17 + 2 + 1 = 20
18 + 2 = 20
3 + 12 + 3 + 2 = 20
18 + 1 + 1 = 20

Using iterative approach -


from random import randint

def sequence(n):

   a, m, c = [], randint(1, n), n   
   while n > m > 0:
      a.append(str(m))
      n -= m
      m = randint(0, n)
   if n: a += [str(n)]
   return ' + '.join(a) + ' = %d' % c

Test code:

for i in xrange(10):
   print sequence(20)

Ouput:

19 + 1 = 20
2 + 15 + 3 = 20
2 + 3 + 12 + 3 = 20
19 + 1 = 20
2 + 10 + 2 + 6 = 20
6 + 3 + 9 + 1 + 1 = 20
14 + 2 + 3 + 1 = 20
3 + 7 + 4 + 4 + 2 = 20
9 + 7 + 3 + 1 = 20
3 + 17 = 20

\$\endgroup\$
  • \$\begingroup\$ I didn't include 0s, as I thought it was not a sum, and the output looks prettier without 0s \$\endgroup\$ – xylon97 Mar 11 '13 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.