Générer les partitions d'un nombre
https://stackoverflow.com/questions/400794
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'avais besoin d'un algorithme pour générer toutes les partitions possibles d'un nombre positif, et j'en ai trouvé une (affichée comme réponse), mais c'est un temps exponentiel.
L’algorithme doit renvoyer toutes les manières possibles d’exprimer un nombre en tant que somme de nombres positifs inférieurs ou égaux à lui-même. Ainsi, 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
Ma question est donc la suivante: existe-t-il un algorithme plus efficace pour cela?
MODIFIER: La question s'intitule "Somme décomposée d'un nombre" , car je ne savais pas vraiment comment elle s'appelait. ShreevatsaR a signalé qu'ils étaient appelés "partitions", " j'ai donc modifié le titre de la question en conséquence.
La solution
Cela s'appelle Partitions . [Voir aussi Wikipedia: Partition (théorie des nombres) .]
Le nombre de partitions p (n) augmente de façon exponentielle. Par conséquent, tout ce que vous faites pour générer toutes doit nécessairement prendre un temps exponentiel.
Cela dit, vous pouvez faire mieux que ce que votre code fait. Voir this ou sa version mise à jour dans Algorithmes Python et structures de données par David Eppstein .
Autres conseils
Voici ma solution (temps exponentiel) en Python:
q = { 1: [[1]] }
def decompose(n):
try:
return q[n]
except:
pass
result = [[n]]
for i in range(1, n):
a = n-i
R = decompose(i)
for r in R:
if r[0] <= a:
result.append([a] + r)
q[n] = result
return result
& nbsp;
>>> decompose(5)
[[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]
Lorsque vous demandez un algorithme plus efficace, je ne sais pas lequel comparer. Mais voici un algorithme écrit de manière simple (Erlang):
-module(partitions).
-export([partitions/1]).
partitions(N) -> partitions(N, N).
partitions(N, Max) when N > 0 ->
[[X | P]
|| X <- lists:seq(min(N, Max), 1, -1),
P <- partitions(N - X, X)];
partitions(0, _) -> [[]];
partitions(_, _) -> [].
Il est exponentiel dans le temps (identique à Can Berk G & # 252; der's solution en Python ) et linéaire dans l’espace pile. Mais en utilisant la même astuce, la mémorisation, vous pouvez réaliser de grandes améliorations en économisant de la mémoire et en minimisant l’exposant. (C'est dix fois plus rapide pour N = 50)
mp(N) ->
lists:foreach(fun (X) -> put(X, undefined) end,
lists:seq(1, N)), % clean up process dictionary for sure
mp(N, N).
mp(N, Max) when N > 0 ->
case get(N) of
undefined -> R = mp(N, 1, Max, []), put(N, R), R;
[[Max | _] | _] = L -> L;
[[X | _] | _] = L ->
R = mp(N, X + 1, Max, L), put(N, R), R
end;
mp(0, _) -> [[]];
mp(_, _) -> [].
mp(_, X, Max, R) when X > Max -> R;
mp(N, X, Max, R) ->
mp(N, X + 1, Max, prepend(X, mp(N - X, X), R)).
prepend(_, [], R) -> R;
prepend(X, [H | T], R) -> prepend(X, T, [[X | H] | R]).
Quoi qu’il en soit, vous devez évaluer votre langue et vos objectifs.
Voici une façon de procéder beaucoup plus longue (c'est ce que j'ai fait avant de connaître le terme "partition", ce qui m'a permis de faire une recherche sur Google):
def magic_chunker (remainder, chunkSet, prevChunkSet, chunkSets):
if remainder > 0:
if prevChunkSet and (len(prevChunkSet) > len(chunkSet)): # counting down from previous
# make a chunk that is one less than relevant one in the prevChunkSet
position = len(chunkSet)
chunk = prevChunkSet[position] - 1
prevChunkSet = [] # clear prevChunkSet, no longer need to reference it
else: # begins a new countdown;
if chunkSet and (remainder > chunkSet[-1]): # no need to do iterations any greater than last chunk in this set
chunk = chunkSet[-1]
else: # i.e. remainder is less than or equal to last chunk in this set
chunk = remainder #else use the whole remainder for this chunk
chunkSet.append(chunk)
remainder -= chunk
magic_chunker(remainder, chunkSet, prevChunkSet, chunkSets)
else: #i.e. remainder==0
chunkSets.append(list(chunkSet)) #save completed partition
prevChunkSet = list(chunkSet)
if chunkSet[-1] > 1: # if the finalchunk was > 1, do further recursion
remainder = chunkSet.pop() #remove last member, and use it as remainder
magic_chunker(remainder, chunkSet, prevChunkSet, chunkSets)
else: # last chunk is 1
if chunkSet[0]==1: #the partition started with 1, we know we're finished
return chunkSets
else: #i.e. still more chunking to go
# clear back to last chunk greater than 1
while chunkSet[-1]==1:
remainder += chunkSet.pop()
remainder += chunkSet.pop()
magic_chunker(remainder, chunkSet, prevChunkSet, chunkSets)
partitions = []
magic_chunker(10, [], [], partitions)
print partitions
>> [[10], [9, 1], [8, 2], [8, 1, 1], [7, 3], [7, 2, 1], [7, 1, 1, 1], [6, 4], [6, 3, 1], [6, 2, 2], [6, 2, 1, 1], [6, 1, 1, 1, 1], [5, 5], [5, 4, 1], [5, 3, 2], [5, 3, 1, 1], [5, 2, 2, 1], [5, 2, 1, 1, 1], [5, 1, 1, 1, 1, 1], [4, 4, 2], [4, 4, 1, 1], [4, 3, 3], [4, 3, 2, 1], [4, 3, 1, 1, 1], [4, 2, 2, 2], [4, 2, 2, 1, 1], [4, 2, 1, 1, 1, 1], [4, 1, 1, 1, 1, 1, 1], [3, 3, 3, 1], [3, 3, 2, 2], [3, 3, 2, 1, 1], [3, 3, 1, 1, 1, 1], [3, 2, 2, 2, 1], [3, 2, 2, 1, 1, 1], [3, 2, 1, 1, 1, 1, 1], [3, 1, 1, 1, 1, 1, 1, 1], [2, 2, 2, 2, 2], [2, 2, 2, 2, 1, 1], [2, 2, 2, 1, 1, 1, 1], [2, 2, 1, 1, 1, 1, 1, 1], [2, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
Voici une solution d'utilisation des paramorphismes que j'ai écrite en Haskell.
import Numeric.Natural (Natural)
import Control.Monad (join)
import Data.List (nub)
import Data.Functor.Foldable (ListF (..), para)
partitions :: Natural -> [[Natural]]
partitions = para algebra
where algebra Nothing = []
algebra (Just (0,_)) = [[1]]
algebra (Just (_, past)) = (nub . (getAll =<<)) (fmap (1:) past)
getAll :: [Natural] -> [[Natural]]
getAll = fmap (dropWhile (==0) . sort) . subsets
where subsets xs = flip sumIndicesAt xs <<*>gt; indices xs
indices :: [Natural] -> [[Natural]]
indices = join . para algebra
where algebra Nil = []
algebra (Cons x (xs, [])) = [[x:xs]]
algebra (Cons x (xs, past)) = (:) <<*>gt; [x:xs,[]] <*> past
Ce n’est certainement pas le plus efficace, mais je pense que c’est plutôt élégant et que c’est certainement instructif.
voici le code java pour cette question
static void printArray(int p[], int n){
for (int i = 0; i < n; i++)
System.out.print(p[i]+" ");
System.out.println();
}
// Function to generate all unique partitions of an integer
static void printAllUniqueParts(int n) {
int[] p = new int[n]; // An array to store a partition
int k = 0; // Index of last element in a partition
p[k] = n; // Initialize first partition as number itself
// This loop first prints current partition, then generates next
// partition. The loop stops when the current partition has all 1s
while (true) {
// print current partition
printArray(p, k + 1);
// Generate next partition
// Find the rightmost non-one value in p[]. Also, update the
// rem_val so that we know how much value can be accommodated
int rem_val = 0;
while (k >= 0 && p[k] == 1) {
rem_val += p[k];
k--;
}
// if k < 0, all the values are 1 so there are no more partitions
if (k < 0){
break;
}
// Decrease the p[k] found above and adjust the rem_val
p[k]--;
rem_val++;
while (rem_val > p[k]) {
p[k + 1] = p[k];
rem_val = rem_val - p[k];
k++;
}
p[k + 1] = rem_val;
k++;
}
}
public static void main(String[] args) {
System.out.println("All Unique Partitions of 5");
printAllUniqueParts(5);
System.out.println("All Unique Partitions of 7");
printAllUniqueParts(7);
System.out.println("All Unique Partitions of 9");
printAllUniqueParts(8);
}
Une autre solution Java. Il commence par créer la première partition qui n’est que le nombre donné. Ensuite, il passe à la boucle while qui recherche le dernier numéro de la dernière partition créée, qui est plus grand que 1. De ce nombre, il passe de 1 au numéro suivant du tableau. Si le nombre suivant finit par être identique au nombre trouvé, il passe au suivant. La boucle s'arrête lorsque le premier numéro de la dernière partition créée est 1. Cela fonctionne car, à tout moment, les numéros de toutes les partitions sont triés par ordre décroissant.
Exemple avec le numéro 5. Premièrement, il crée la première partition qui n’est que le numéro 5. Ensuite, il trouve le dernier numéro de la dernière partition qui est supérieur à 1. Puisque notre dernière partition est un tableau [5, 0, 0, 0, 0] il fonde le numéro 5 à l'index 0. Ensuite, il en passe un à 5 et le déplace à la position suivante. C'est ainsi que nous obtenons la partition [4, 1, 0, 0, 0]. Il va à nouveau dans la boucle. Maintenant, il en faut un de 4 et le déplace vers le haut pour obtenir [3, 2, 0, 0, 0]. Ensuite, la même chose et nous obtenons [3, 1, 1, 0, 0]. À la prochaine itération, nous obtenons [2, 2, 1, 0, 0]. Maintenant, il en faut un à partir de la seconde 2 et essaie de le déplacer vers l’index 2 où nous avons 1. Il passera à l’index suivant car nous aurions aussi 2 et nous aurions une partition [2, 1, 2, 0, 0] qui est juste une copie du dernier. au lieu de cela nous obtenons [2, 1, 1, 1, 0]. Et dans la dernière étape, nous arrivons à [1, 1, 1, 1, 1] et la boucle existe car le premier numéro de la nouvelle partition est égal à 1.
private static List<int[]> getNumberPartitions(int n) {
ArrayList<int[]> result = new ArrayList<>();
int[] initial = new int[n];
initial[0] = n;
result.add(initial);
while (result.get(result.size() - 1)[0] > 1) {
int[] lastPartition = result.get(result.size() - 1);
int posOfLastNotOne = 0;
for(int k = lastPartition.length - 1; k >= 0; k--) {
if (lastPartition[k] > 1) {
posOfLastNotOne = k;
break;
}
}
int[] newPartition = new int[n];
for (int j = posOfLastNotOne + 1; j < lastPartition.length; j++) {
if (lastPartition[posOfLastNotOne] - 1 > lastPartition[j]) {
System.arraycopy(lastPartition, 0, newPartition, 0, lastPartition.length);
newPartition[posOfLastNotOne]--;
newPartition[j]++;
result.add(newPartition);
break;
}
}
}
return result;
}
Implémentation Java. Pourrait bénéficier de la mémorisation.
public class Partition {
/**
* partition returns a list of int[] that represent all distinct partitions of n.
*/
public static List<int[]> partition(int n) {
List<Integer> partial = new ArrayList<Integer>();
List<int[]> partitions = new ArrayList<int[]>();
partition(n, partial, partitions);
return partitions;
}
/**
* If n=0, it copies the partial solution into the list of complete solutions.
* Else, for all values i less than or equal to n, put i in the partial solution and partition the remainder n-i.
*/
private static void partition(int n, List<Integer> partial, List<int[]> partitions) {
//System.out.println("partition " + n + ", partial solution: " + partial);
if (n == 0) {
// Complete solution is held in 'partial' --> add it to list of solutions
partitions.add(toArray(partial));
} else {
// Iterate through all numbers i less than n.
// Avoid duplicate solutions by ensuring that the partial array is always non-increasing
for (int i=n; i>0; i--) {
if (partial.isEmpty() || partial.get(partial.size()-1) >= i) {
partial.add(i);
partition(n-i, partial, partitions);
partial.remove(partial.size()-1);
}
}
}
}
/**
* Helper method: creates a new integer array and copies the contents of the list into the array.
*/
private static int[] toArray(List<Integer> list) {
int i = 0;
int[] arr = new int[list.size()];
for (int val : list) {
arr[i++] = val;
}
return arr;
}
}
