Erstellen der Partitionen einer Nummer

Question

Ich brauchte einen Algorithmus, um alle möglichen Partitionen einer positiven Zahl zu generieren, und ich kam mit einem (als Antwort), aber es ist exponentielle Zeit.

Der Algorithmus sollte alle möglichen Möglichkeiten zurückgeben, wie eine Zahl als Summe positiver Zahlen kleiner oder gleich wie sich selbst ausgedrückt werden kann. So werden zum Beispiel für die Anzahl , würde das Ergebnis sein:

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

Meine Frage ist also: Gibt es einen effizienteren Algorithmus dafür?

EDIT: Frage stand unter dem Titel „Sum Zerlegung einer Zahl“, da ich nicht wirklich wusste, was das hieß. ShreevatsaR pointed out, dass sie "Partitionen" genannt wurden, also habe ich den Fragetitel entsprechend bearbeitet.

Answer 1

Es Partitions genannt wird. [Siehe auch Wikipedia:. Partition (number theory)]

Die Anzahl der Partitionen p (n) wächst exponentiell, so alles, was Sie alle Partitionen zu erzeugen, wird notwendigerweise exponentielle Zeit in Anspruch nehmen müssen.

Das heißt, Sie können besser als das, was Ihr Code tut. Siehe this oder die aktualisierte Version in Python Algorithms and Data Structures von David Eppstein.

Answer 2

Hier ist meine Lösung (exponentielle Zeit) in 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

Wenn Sie nach effizienteren Algorithmus fragen, weiß ich nicht, zu vergleichen. Aber hier ist ein Algorithmus in geradlinig Weg (Erlang) geschrieben:

-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 ist exponentiell in der Zeit (das gleiche wie Can Berk Güder's solution in Python) und linear in Stapelspeicher. Aber mit demselben Trick, Memoization, können Sie große Verbesserung erreichen, indem Sie etwas Speicher und weniger Exponent sparen. (Es ist zehnmal schneller für N = 50)

Wie auch immer sollten Sie Benchmark für Ihre Sprache und Zwecke.

Answer 4

Java-Implementierung. Könnte von einer Memoisierung profitieren.

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

Hier ist eine viel langatmige Art und Weise, es zu tun (das ist, was ich tat, bevor ich den Begriff „Partition“ wusste, das es mir ermöglicht, eine Google-Suche zu tun):

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

Hier ist eine Lösung für die Verwendung von Paramorphismen, die ich in Haskell geschrieben habe.

Es ist definitiv nicht das effizienteste um, aber ich denke, es ist ziemlich elegant und es ist sicherlich lehrreich.