Code Python élégant pour le partitionnement entier

Question

J'ai essayé d'écrire du code pour résoudre le problème standard de la partition entière ( Wikipedia ). Le code que j'ai écrit était un gâchis. J'ai besoin d'une solution élégante pour résoudre le problème, car je veux améliorer mon style de codage. Ce n'est pas une question de devoirs.

Answer 1

Bien que cette réponse soit correcte, je recommanderais la réponse de skovorodkin ci-dessous :

 >>> 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,)])

Si vous voulez toutes les permutations (c'est-à-dire (1, 3) et (3, 1)) changez answer.add(tuple(sorted((x, ) + y)) en answer.add((x, ) + y)

Answer 2

J'avais besoin de résoudre un problème similaire , à savoir la partition d'un entier n en d parties non négatives, avec des permutations. Pour cela, il existe une solution récursive simple (voir ici ):

 def partition(n, d, depth=0):
    if d == depth:
        return [[]]
    return [
        item + [i]
        for i in range(n+1)
        for item in partition(n-i, d, depth=depth+1)
        ]


# extend with n-sum(entries)
n = 5
d = 3
lst = [[n-sum(p)] + p for p in partition(n, d-1)]

print(lst)

Sortir:

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