brianpck - 9 months ago 33

Python Question

I am experimenting with recursive functions. My goal is to produce:

A functionthat generates all non-increasing series that add up to n`combo`

Some sample inputs/outputs:

`>>> print (combo(3))`

[[3], [2, 1], [1, 1, 1]]

>>> print (combo(4))

[[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]

>>> print (combo(5))

[[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]

After a lot of trial and error, I came up with the following function which does exactly what I want:

`def combo(n, limit=None):`

if not limit:

limit = n

# return [ LIST COMPREHENSION HERE ]

res = []

for i in range(limit, 0, -1):

if i == n:

res.append([i])

else:

res.extend([i] + x for x in combo(n - i, min(n - i, i)))

return res

My question:

`res`

Here are two things I've tried, along with their mangled results:

`return [[i] if i == n else [[i] + x for x in combo(n - i, min(n - i, i))] for i in range(limit, 0, -1)]`

# lists get deeper: [[4], [[3, 1]], [[2, 2], [2, [1, 1]]], [[1, [1, [1, 1]]]]]

return [[i if i == n else ([i] + x for x in combo(n - i, min(n - i, i))) for i in range(limit, 0, -1)]]

# parentheses interpreted as generator: [[4, <generator object combo.<locals>.<listcomp>.<genexpr> at 0x01D84E40>, etc.]]

I realize that the answer may be quite ugly, but I've spent enough time trying that I just want to know if it is

Answer

Convert *extending* to *appending* and it becomes easier to grok how to convert this:

```
res = []
for i in range(limit, 0, -1):
if i == n:
res.append([i])
else:
# this is the generator expression pulled out of the res.extend() call
for x in combo(n - i, min(n - i, i)):
res.append([i] + x)
```

You can now move the `i == n`

case into the other branch (using a helper `items`

variable here for readability):

```
res = []
for i in range(limit, 0, -1):
items = [[]] if i == n else combo(n - i, min(n - i, i))
for x in items:
res.append([i] + x)
```

If `i == n`

, this causes the loop iterate once and produce an empty list, so you effectively get `res.append([i])`

.

This can then trivially be converted to a list comprehension (inlining `items`

into the `for`

loop):

```
return [
[i] + x
for i in range(limit, 0, -1)
for x in ([[]] if i == n else combo(n - i, min(n - i, i)))]
```

Wether or not you *should* is another matter; this is hardly easier to read.

Source (Stackoverflow)