Generowanie partycji o numerze

Question

Potrzebowałem algorytmu do wygenerowania wszystkich możliwych partycji liczby dodatniej, a ja wymyśliłem jedną (wysłaną jako odpowiedź), ale jest to wykładniczy czas.

Algorytm powinien zwrócić wszystkie możliwe sposoby wyrażenia liczby jako sumę liczb dodatnich mniejszych lub równych sobie. Tak na przykład dla liczby wynik to:

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

Moje pytanie brzmi: czy istnieje bardziej wydajny algorytm?

EDIT: Pytanie została zatytułowana „Sum dekompozycję szeregu”, bo tak naprawdę nie wiem, co to było nazywane. ShreevatsaR pointed out, które nazwano "partycjami", więc odpowiednio zredagowałem tytuł pytania.

Answer 1

Nazywa Partitions. [Patrz także Wikipedia:. Partition (number theory)]

liczby partycji p (n) rośnie wykładniczo, więc coś zrobić, aby wygenerować wszystkie partycji koniecznie trzeba wziąć wykładniczą czasu.

Powiedziawszy, możesz zrobić lepiej niż to, co robi twój kod. Zobacz this lub jego zaktualizowaną wersję w Python Algorithms and Data Structures przez David Eppstein.

Answer 2

Oto moje rozwiązanie (czas wykładniczy) w Pythonie:

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

Gdy pytasz o bardziej efektywny algorytm, nie wiem, które porównanie. Ale tutaj jest jeden algorytm napisany w prosty sposób do przodu (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(_, _) -> []. 

Jest wykładniczy w czasie (tak samo jak Can Berk Güder's solution in Python) i liniowy w przestrzeni stosu. Ale używając tej samej sztuczki, zapamiętywania, możesz osiągnąć dużą poprawę, oszczędzając pamięć i mniej wykładników. (Dziesięć razy szybciej dla 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]). 

W każdym razie powinieneś sprawdzić swój język i cele.

Answer 4

Implementacja Java. Może skorzystać z memoizacji.

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

Oto znacznie bardziej rozwlekły sposób to zrobić (jest to co zrobiłem przed Wiedziałem, termin „partycji”, który pozwolił mi zrobić wyszukiwania 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

Oto rozwiązanie w stosowaniu paramorfizmów, które napisałem w 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 

Z pewnością nie jest to najbardziej wydajny model, ale uważam, że jest dość elegancki i na pewno jest pouczający.