Generando las particiones de un número

Question

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 expresar como la suma de números positivos menores o iguales a sí mismo. Así, por ejemplo para el número , el resultado sería:

• 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?

EDIT: pregunta se tituló "descomposición suma de un número", ya que no sabía muy bien lo que esto fue llamado. ShreevatsaR pointed out que se llamaron "particiones", así que edité el título de la pregunta en consecuencia.

Answer 1

Se llama Partitions. [Véase también Wikipedia:. Partition (number theory)]

El número de particiones p (n) crece de forma exponencial, por lo que cualquier cosa que haga para generar todas las particiones necesariamente tendrá que tomar tiempo exponencial.

Dicho esto, puede hacer algo mejor que lo que hace su código. Consulte this, o su versión actualizada en Python Algorithms and Data Structures por David Eppstein.

Answer 2

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 = n-i 
     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]] 

Answer 3

Cuando pregunta a un algoritmo más eficiente, no sé cuál comparar. Pero aquí es un algoritmo, escrita en forma recta hacia adelante (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 (igual que Can Berk Güder's solution in Python) y lineal en el espacio de pila. 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 lengua y sus propósitos.

Answer 4

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

Answer 5

Aquí está una manera mucho más largo aliento de hacerlo (esto es lo que hice antes de saber que el término "partición", lo 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: # 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]] 

Answer 6

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.