生成一个数字的分区
我需要一个algorithm来生成一个正数的所有可能的分区，我想出了一个（作为答案张贴），但它是指数的时间。
该algorithm应该返回所有可能的方式，一个数字可以表示为小于或等于自身的正数的总和。 因此，例如对于数字5 ，结果将是：
- 五
- 4 + 1
- 3 + 2
- 3 + 1 + 1
- 2 + 2 + 1
- 2 + 1 + 1 + 1
- 1 + 1 + 1 + 1 + 1
所以我的问题是：是否有一个更有效的algorithm呢？
编辑：问题题为“总和分解的一个数字” ，因为我真的不知道这是什么叫。 ShreevatsaR指出 ，他们被称为“分区”，所以我相应地编辑了问题标题。
这就是所谓的分区 。 [也见维基百科： 分区（数字理论） 。]
分区p（n）的数量呈指数增长，所以你所做的任何生成所有分区的操作都必须花费指数时间。
也就是说，你可以比你的代码做得更好。 请参阅David Eppstein的“ Pythonalgorithm和数据结构”中的更新版本。
这是我的解决scheme（指数时间）在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]]
当你问到更高效的algorithm，我不知道要比较哪个。 但是这里有一个直接写法的algorithm（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(_, _) -> [].
它的时间呈指数级增长（与Python中的Can BerkGüder解决scheme相同），并且在堆栈空间中是线性的。 但使用相同的技巧，记忆，你可以通过节省一些内存和较less的指数来实现大的改进。 （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]).
无论如何，你应该为你的语言和目的设定基准。
这里有一个更为冗长的做法（这是我知道术语“分区”之前所做的，它使我能够进行谷歌search）：
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]]
这是使用我在Haskell中编写的paramorphisms的一个解决scheme。
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
这绝对不是最有效率的，但我认为这是相当优雅的，这是有启发性的。
Java实现。 可以从memoization中受益。
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 ni. */ 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(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<Integer> list) { int i = 0; int[] arr = new int[list.size()]; for (int val : list) { arr[i++] = val; } return arr; } }
