Générer les partitions d'un nombre

Question

J'avais besoin d'un algorithme pour générer toutes les partitions possibles d'un nombre positif, et j'en ai trouvé un (affiché comme réponse), mais c'est un temps exponentiel.

L'algorithme doit retourner toutes les manières possibles d'exprimer un nombre comme la somme des nombres positifs inférieurs ou égaux à lui-même. Ainsi, par exemple pour le nombre , le résultat serait:

• 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: y a-t-il un algorithme plus efficace?

EDIT: Question a été intitulé « décomposition de la somme d'un certain nombre », puisque je ne savais pas vraiment ce que cela a été appelé. ShreevatsaR pointed out qu'ils ont été appelés "partitions", alors j'ai édité le titre de la question en conséquence.

Answer 1

Il est appelé Partitions. [Voir aussi Wikipédia:. Partition (number theory)]

Le nombre de partitions p (n) croît de façon exponentielle, donc tout ce que vous faites pour générer toutes les partitions va nécessairement prendre du temps exponentielle.

Cela dit, vous pouvez faire mieux que votre code. Voir this, ou sa version mise à jour dans Python Algorithms and Data Structures par David Eppstein.

Answer 2

Voici ma solution (temps exponentielle) 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

Lorsque vous demandez un algorithme plus efficace, je ne sais pas lequel comparer. Mais voici un algorithme écrit en voie à suivre droite (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 exponentielle dans le temps (comme Can Berk Güder's solution in Python) et linéaire dans l'espace de la pile. Mais en utilisant la même astuce, mémo, vous pouvez réaliser de grandes améliorations en économisant de la mémoire et moins d'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]). 

De toute façon, vous devriez référencer votre langue et vos objectifs.

Answer 4

Implémentation Java. Pourrait bénéficier de la mémo.

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

Voici une manière beaucoup plus longue haleine de le faire (ce qui est ce que je faisais avant que je connaissais le terme « partition », ce qui m'a permis de faire une recherche 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

Voici une solution pour utiliser les paramorphismes que j'ai écrits dans Haskell. Ce n'est certainement pas le plus efficace, mais je pense que c'est assez élégant et c'est certainement instructif.