Générer les partitions d'un certain nombre
J'ai besoin d'un algorithme permettant de générer toutes les partitions possibles d'un nombre positif, et je suis venu avec un (affichée comme réponse), mais il est temps exponentiel.
L'algorithme doit retourner tous les moyens possibles un certain nombre peut être exprimé comme la somme de nombres positifs est inférieur ou égal à lui-même. Donc par exemple pour le nombre 5, le résultat serait:
- 5
- 4+1
- 3+2
- 3+1+1
- 2+2+1
- 2+1+1+1
- 1+1+1+1+1
Donc ma question est: est-il un algorithme plus efficace pour cela?
EDIT: Question a été intitulé "la Somme de décomposition d'un nombre", car je ne savais pas vraiment ce que cela a été appelé. ShreevatsaR souligné qu'ils étaient appelés des "partitions", donc j'ai édité la question du titre en conséquence.
- Juste par curiosité: est-ce une question théorique (qui est OK) ou c'est une mise en pratique?
- Il a une utilisation pratique pour moi. J'ai besoin de générer toutes les partitions d'un nombre N. Chaque partition correspond à une distribution différente, et donc un autre "couverture" de la valeur, que je suis en train de l'optimiser.
- Si vous êtes à la recherche pour simplement le nombre de partitions et de ne pas la formule, il y a une forme fermée solution.
- Qu'est-ce que cette solution de la forme finie?
- Je n'ai pas envie d'ajouter une nouvelle réponse ou de la modification de la mine, mais note que Knuth traite des algorithmes de génération de toutes les partitions dans la Section 7.2.1.4 (Volume 4A de L'Art de la Programmation Informatique). Une première ébauche de cet article est disponible en ligne. (PDF, PS)
- Intéressant de noter qu'il y a une connexion à la 'pièce de monnaie problème du changement" ou "pièces de monnaies de problème", qui a Dynamique des solutions de Programmation, si vous êtes seulement en considérant les partitions plus restreint des ensembles d'entiers (pièces particulières).
Vous devez vous connecter pour publier un commentaire.
Il est appelé Partitions. [Voir aussi Wikipédia: Partition (théorie des nombres).]
Le nombre de partitions p(n) croît de façon exponentielle, donc tout ce que vous faire pour générer tous partitions devra nécessairement prendre le temps exponentiel.
Cela dit, vous pouvez faire mieux que ce que votre code ne. Voir cette, ou sa version mise à jour en Python Algorithmes et Structures de Données par David Eppstein.
Voici ma solution (temps exponentiel) en Python:
Lorsque vous demandez d'algorithme plus efficace, je ne sais pas qui à comparer. Mais en voici un algorithme écrit en simple (Erlang):
Elle est exponentielle dans le temps (le même que Peut Berk Güder de la solution en Python) et linéaire dans l'espace de pile. Mais en utilisant la même astuce, memoization, vous pouvez obtenir une grande amélioration par économiser de la mémoire et de moins en moins d'exposant. (C'est dix fois plus rapide pour N=50)
De toute façon, vous devriez référence pour votre langue et fins.
Voici une beaucoup plus longue haleine moyen de le faire (c'est ce que j'ai fait avant, je savais que le terme "partition", ce qui m'a permis de faire une recherche sur google):
Voici une solution en utilisant paramorphisms que j'ai écrit en Haskell.
Ce n'est certainement pas la plus efficace, mais je pense que c'est très élégant et il est certainement instructif.
voici le code java pour cette question
Une autre solution Java. Il commence par la création de la première partition qui est seulement le nombre donné. Puis il va dans la boucle while qui est de trouver le dernier numéro dans la dernière création de la partition qui est plus grand que 1. De ce nombre, il se déplace de 1 à nombre suivant dans la gamme. Si le prochain numéro est le même que le trouvé, il se déplace vers le prochain dans la ligne. La boucle s'arrête lorsque le premier numéro de la dernière création de la partition est de 1. Cela fonctionne, car à tout moment les numéros de toutes les partitions sont triés dans l'ordre décroissant.
Exemple avec le numéro 5. D'abord, il crée la première partition qui est juste le numéro 5. Il trouve ensuite le dernier numéro de la dernière partition qui est supérieure à 1. Depuis notre dernière partition est la matrice de [5, 0, 0, 0, 0] il fonde le numéro 5 à l'indice 0. Puis il prend un 5 et le déplace à la position suivante. C'est ce qui nous partition [4, 1, 0, 0, 0]. Il va dans la boucle à nouveau. Maintenant, il prend un 4 et le déplace de façon à ce que nous obtenir [3, 2, 0, 0, 0]. Puis la même chose et nous obtenons [3, 1, 1, 0, 0]. Sur la prochaine itération nous obtenons [2, 2, 1, 0, 0]. Maintenant, il prend un deuxième 2 et tente de passer à l'indice 2, où nous avons 1. Il vous permettra de passer au suivant index parce que nous aussi obtenir la 2 et nous aurions partition [2, 1, 2, 0, 0] qui est juste dupliquer le dernier. la place, nous avons [2, 1, 1, 1, 0]. Et dans la dernière étape, nous arrivons à [1, 1, 1, 1, 1] et la boucle qui existe depuis le premier numéro de la nouvelle partition est 1.
Implémentation de Java. Pourraient bénéficier de memoization.