algorithm - Elegant Python code for Integer Partitioning

Question

(Closed). This question needs to be more focused. It is not currently accepting answers. question from:https://stackoverflow.com/questions/10035752/elegant-python-code-for-integer-partitioning

Answer 1

While this answer is fine, I'd recommend skovorodkin's answer below:

>>> def partition(number):
...     answer = set()
...     answer.add((number, ))
...     for x in range(1, number):
...         for y in partition(number - x):
...             answer.add(tuple(sorted((x, ) + y)))
...     return answer
... 
>>> partition(4)
set([(1, 3), (2, 2), (1, 1, 2), (1, 1, 1, 1), (4,)])

If you want all permutations(ie (1, 3) and (3, 1)) change answer.add(tuple(sorted((x, ) + y)) to answer.add((x, ) + y)