Generando las particiones de un número

Necesitaba un algoritmo para generar todas las particiones posibles de un número positivo, y se me ocurrió una (publicada como respuesta), pero es un tiempo exponencial.

El algoritmo debe devolver todas las formas posibles en que un número se puede express como la sum de números positivos menores o iguales a sí mismo. Entonces, por ejemplo, para el número 5 , el resultado sería:

  • 5
  • 4 + 1
  • 3 + 2
  • 3 + 1 + 1
  • 2 + 2 + 1
  • 2 + 1 + 1 + 1
  • 1 + 1 + 1 + 1 + 1

Entonces mi pregunta es: ¿hay un algoritmo más eficiente para esto?

EDITAR: La pregunta se tituló “Suma descomposición de un número” , ya que realmente no sabía cómo se llamaba. ShreevatsaR señaló que se llamaban “particiones”, por lo que edité el título de la pregunta en consecuencia.

Se llama particiones . [También vea Wikipedia: Partición (teoría de números) .]

El número de particiones p (n) crece exponencialmente, por lo que todo lo que hagas para generar todas las particiones necesariamente tendrá que tomar un tiempo exponencial.

Dicho esto, puedes hacer mejor que lo que hace tu código. Vea esto , o su versión actualizada en Algoritmos de Python y Estructuras de Datos por David Eppstein .

Aquí está mi solución (tiempo exponencial) en Python:

q = { 1: [[1]] } def decompose(n): try: return q[n] except: pass result = [[n]] for i in range(1, n): a = ni R = decompose(i) for r in R: if r[0] <= a: result.append([a] + r) q[n] = result return result 

 >>> decompose(5) [[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]] 

Cuando pides un algoritmo más eficiente, no sé a cuál comparar. Pero aquí hay un algoritmo escrito de manera directa (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(_, _) -> []. 

Es exponencial en el tiempo (lo mismo que la solución de Can Berk Güder en Python ) y lineal en el espacio de stack. Pero usando el mismo truco, la memorización, puede lograr una gran mejora guardando algo de memoria y menos exponente. (Es diez veces más rápido para 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]). 

De todos modos, debe comparar su idioma y propósitos.

Aquí hay una manera mucho más prolija de hacerlo (esto es lo que hice antes de conocer el término “partición”, que me permitió hacer una búsqueda en 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: # ie 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: #ie 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: #ie 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]] 

Aquí hay una solución para usar paramorfismos que escribí 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 <$> indices xs indices :: [Natural] -> [[Natural]] indices = join . para algebra where algebra Nil = [] algebra (Cons x (xs, [])) = [[x:xs]] algebra (Cons x (xs, past)) = (:) <$> [x:xs,[]] <*> past 

Definitivamente no es el más eficiente, pero creo que es bastante elegante y ciertamente instructivo.

aquí está el código de Java para esta pregunta

 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); } 

Implementación de Java. Podría beneficiarse de la memorización.

 public class Partition { /** * partition returns a list of int[] that represent all distinct partitions of n. */ public static List partition(int n) { List partial = new ArrayList(); List partitions = new ArrayList(); 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 ni. */ private static void partition(int n, List partial, List 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(ni, 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 list) { int i = 0; int[] arr = new int[list.size()]; for (int val : list) { arr[i++] = val; } return arr; } }