Python integer partitioning

Question

I am trying to write a piece of code that will give me the partitions of a number.So far I came up with this(found on google).

def gen(n):
           # tuple version
           if n == 0:
               yield ()
               return

           for p in gen(n-1):
               yield (1, ) + p
               if p and (len(p)<2 or p[1] > p[0]):
                   yield (p[0] + 1, ) + p[1:]

print(list(gen(5)))

I would really appreciate if someone could help me understand how this Recursive function works.Please help.Thank you.

I would really love if you can please explain every single line please.That will help me understand better how yield works.Thank you — Serj Codito, Feb 21 '13 at 20:46
possible duplicate of [The Python yield keyword explained](http://stackoverflow.com/questions/231767/the-python-yield-keyword-explained) — Robᵩ, Feb 21 '13 at 20:50
I've read that before and I did understand how yield work.But that doesn't answer my question.I still cannot understand why he wrote yield() then return and why he wrote yield(1,)+p.That's what confuses me.Could you please explain to me how this works.Thank you. — Serj Codito, Feb 21 '13 at 20:55
1) All generators have to `return` after they have `yield`ed their final result. Usually the return is implicit when they fall off the bottom of the function. (Contemplate [this program](http://ideone.com/MYAHC2)) 2) `yield (1,)+p` is part of his recursive algorithm. That expression creates a tuple with `1` as the initial element and the members of `p` as the remaining elements. So if, for example, `(2,2)` is a partition of the number 4, then `(1,2,2)` is a partition of the number 5. — Robᵩ, Feb 21 '13 at 21:08
Because you can add tuples in Python: `(3,)+(1,)==(3,1)` and `()+(3,)==(3,)` and `if n==0: yield (); return` breaks recursion... — dawg, Feb 21 '13 at 21:27

score 3 · Answer 1 · answered Feb 21 '13 at 23:32

To understand what's going on, it helps to print the output of the generator for several sequentially increasing values of n:

>>> for i in range(5):
        print(list(gen(i)))

[()]
[(1,)]
[(1, 1), (2,)]
[(1, 1, 1), (1, 2), (3,)]
[(1, 1, 1, 1), (1, 1, 2), (2, 2), (1, 3), (4,)]

The computation of each sequence is based on the one before it. Here's a line-by line explanation of how it works:

if n == 0:
    yield ()
    return

These first few lines of the generator are for the base case, where n is zero. The return statement makes it exit after yielding an empty tuple, rather than continuing on with the rest of the code.

for p in gen(n-1):

This is the recursive step of the function. Since gen is a generator, it's done with a loop, so the rest of the code will run repeatedly with p taking different values from the results of the recursion.

    yield (1, ) + p

This is an important line. What this does is yield out of the generator a new tuple formed by concatenating a 1 onto the front of the value p. If p was the empty tuple, this will be a 1-tuple. If p already had some values, the tuple will become longer.

    if p and (len(p)<2 or p[1] > p[0]):

This is a complicated condition. The second check, len(p)<2 could really be written len(p)==1, since the p and part at the start has already ruled out p being empty.

There are two kinds of values that p can have, in order to pass. Either p has exactly one value, or it has more values, and its first value is less than its second value. So (3,) will pass, as will (1,2), but (1,1,1) will not.

        yield (p[0] + 1, ) + p[1:]

This is another tuple concatenation. It's increasing the first value of p by one and then concatenating it with the rest of p (using a slice). So (3,) will become (4,) (with the slice being empty), (1,2) becomes (2,2), etc.

So, now lets run through the results we saw above.

[()]

With n equal to 0, the base case is hit and you get a single empty tuple yielded.

[(1,)]

With n equal to 1, the loop runs one time, and concatenates (1,) onto the empty tuple, yielding the 1-tuple (1,). The first part of the if condition is not passed, since p is empty.

[(1,1), (2,)]

With n equal to 2, the loop still only runs once. First it yields (1,1) by concatenating (1,) with itself to get (1,1). But this time, the if block is run because p had just a single value. So it also yields (p[0]+1,) + p[1:]. The slice part of that is the empty tuple, but the first part is (2,).

[(1,1,1), (1,2), (3,)]

Now finally the loop gets to run more than once! The first time though, it concatenates another (1,) onto the front of (1,1), and since the if statement's conditions are not met, that's all it does. On the second pass however, it yields two values, once concatenating (1,) and (2,) and then incrementing (2,) to (3,).

[(1, 1, 1, 1), (1, 1, 2), (2, 2), (1, 3), (4,)]

This one I'll leave to you, to walk through. Like the cases above, p will take on each of the values from the previous level of call ((1,1,1), (1,2), (3,)) and for each value it will yield either one or two new results.

I really appreciate what you have wrote and thank you for taking the time writing all of this.It helped me a lot and I hope it helps other people too. — Serj Codito, Feb 22 '13 at 00:13
@SerjCodito If this answer helped you, and you feel it answered your question adequately you should accept it(and possibly upvote) — entropy, Feb 22 '13 at 00:32

score 0 · Answer 2 · edited May 23 '17 at 10:32

0

yield turns your function into a generator. Read this answer for a good explanation.

Basically, instead of creating a list of results at once and then returning it:

def f():
    output = []

    for i in range(10):
        output.append(i + 3)

    return output

You can create a generator that yields items only when you request one:

def f():
    for i in range(10):
        yield i + 3

It's also possible to make infinite generators:

def f():
    a = 0
    b = 1

    while True:
        yield b

        a, b = b, a + b

Iterating over f() will just keep spitting out terms of the Fibonacci sequence.

edited May 23 '17 at 10:32

Community

1
1

answered Feb 21 '13 at 20:52

Blender

289,723
53
439
496

Thank you,but I already know what you've wrote.Thing is that I don't understand why he wrote yield() then return and why how this -> yield (1, ) + p works.Can you please explain – Serj Codito Feb 21 '13 at 20:59

Python integer partitioning

2 Answers2