Generating the partitions of a number

Question

I needed an algorithm to generate all possible partitions of a positive number, and I came up with one (posted as an answer), but it's exponential time.

The algorithm should return all the possible ways a number can be expressed as the sum of positive numbers less than or equal to itself. So for example for the number 5, the result would be:

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

So my question is: is there a more efficient algorithm for this?

EDIT: Question was titled "Sum decomposition of a number", since I didn't really know what this was called. ShreevatsaR pointed out that they were called "partitions," so I edited the question title accordingly.

• PhiLho: Just curious: is that a theoretical question (which is OK) or does it has a practical use?
• Can Berk Güder: It does have a practical use for me. I need to generate all partitions of a number N. Each partition corresponds to a different distribution, and therefore a different "coverage" value, which I'm trying to maximize.
• AlexQueue: If you're looking for simply the number of partitions and not the specific formula, there is a closed-form solution.
• Steve Byrne: What is that closed form solution?
• ShreevatsaR: I don't feel like adding a new answer or editing mine, but note that Knuth discusses algorithms for generating all partitions in Section 7.2.1.4 (Volume 4A of The Art of Computer Programming). An early draft of this section is available online. (PDF, PS)

Answer 1

It's called Partitions. [Also see Wikipedia: Partition (number theory).]

The number of partitions p(n) grows exponentially, so anything you do to generate all partitions will necessarily have to take exponential time.

That said, you can do better than what your code does. See this, or its updated version in Python Algorithms and Data Structures by David Eppstein.

• Can Berk Güder: Oh, thanks. Wish I knew what it was called before. =) It's funny they don't teach this in Number Theory.
• user49117: Thanks for the link to David Eppstein's site, just finished an interesting browsing on his site.
• ShreevatsaR: He moved his blog; the last link is now here.

Answer 2

Here's my solution (exponential time) 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]]

• Jay: You can't get any better than exponential, since there is an exponential number of partitions!

Answer 3

When you ask to more efficient algorithm, I don't know which to compare. But here is one algorithm written in straight forward way (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(_, _) -> [].

It is exponential in time (same as Can Berk Güder's solution in Python) and linear in stack space. But using same trick, memoization, you can achieve big improvement by save some memory and less exponent. (It's ten times faster for 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]).

Anyway you should benchmark for your language and purposes.

Answer 4

Here's a much more long-winded way of doing it (this is what I did before I knew the term "partition", which enabled me to do a google 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: # 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]]

• ShreevatsaR: No need to be so self-deprecating! Have you tested that this works? How do you call this function? Is there an example?
• johnbasil: thanks @ShreevatsaR, yes it does work and I've now made it into a full example

Answer 5

Java implementation. Could benefit from 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 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 6

Here's a solution in using paramorphisms that I wrote in 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

It's definitely not the most efficient one around, but I think it's quite elegant and it's certainly instructive.

Answer 7

here is the java code for this question

static void printArray(int p[], int n){
 for (int i = 0; i < n; i++)
 System.out.print(p[i]+" ");
 System.out.println();
}
// Function to generate all unique partitions of an integer
static void printAllUniqueParts(int n) {
 int[] p = new int[n]; // An array to store a partition
 int k = 0; // Index of last element in a partition
 p[k] = n; // Initialize first partition as number itself
 // This loop first prints current partition, then generates next
 // partition. The loop stops when the current partition has all 1s
 while (true) {
 // print current partition
 printArray(p, k + 1);
 // Generate next partition
 // Find the rightmost non-one value in p[]. Also, update the
 // rem_val so that we know how much value can be accommodated
 int rem_val = 0;
 while (k >= 0 && p[k] == 1) {
 rem_val += p[k];
 k--;
 }
 // if k < 0, all the values are 1 so there are no more partitions
 if (k < 0){
 break;
 }
 // Decrease the p[k] found above and adjust the rem_val
 p[k]--;
 rem_val++;
 while (rem_val > p[k]) {
 p[k + 1] = p[k];
 rem_val = rem_val - p[k];
 k++;
 }
 p[k + 1] = rem_val;
 k++;
 }
}
public static void main(String[] args) {
 System.out.println("All Unique Partitions of 5");
 printAllUniqueParts(5);
 System.out.println("All Unique Partitions of 7");
 printAllUniqueParts(7);
 System.out.println("All Unique Partitions of 9");
 printAllUniqueParts(8);
}

• arashka: Please explain your answer.

Answer 8

Another Java solution. It starts by creating first partition which is only the given number. Then it goes in while loop which is finding the last number in last created partition which is bigger then 1. From that number it moves 1 to next number in array. If next number would end up being the same as the found number it moves to the next in line. Loop stops when first number of last created partition is 1. This works because at all times numbers in all partitions are sorted in descending order.

Example with number 5. First it creates first partition which is just number 5. Then it finds last number in last partition that is greater then 1. Since our last partition is array [5, 0, 0, 0, 0] it founds number 5 at index 0. Then it takes one from 5 and moves it to next position. That is how we get partition [4, 1, 0, 0, 0]. It goes into the loop again. Now it takes one from 4 and moves it up so we get [3, 2, 0, 0, 0]. Then the same thing and we get [3, 1, 1, 0, 0]. On next iteration we get [2, 2, 1, 0, 0]. Now it takes one from second 2 and tries to move it to index 2 where we have 1. It will skip to the next index because we would also get 2 and we would have partition [2, 1, 2, 0, 0] which is just duplicate of the last one. instead we get [2, 1, 1, 1, 0]. And in the last step we get to [1, 1, 1, 1, 1] and loop exists since first number of new partition is 1.

private static List<int[]> getNumberPartitions(int n) {
 ArrayList<int[]> result = new ArrayList<>();
 int[] initial = new int[n];
 initial[0] = n;
 result.add(initial);
 while (result.get(result.size() - 1)[0] > 1) {
 int[] lastPartition = result.get(result.size() - 1);
 int posOfLastNotOne = 0;
 for(int k = lastPartition.length - 1; k >= 0; k--) {
 if (lastPartition[k] > 1) {
 posOfLastNotOne = k;
 break;
 }
 }
 int[] newPartition = new int[n];
 for (int j = posOfLastNotOne + 1; j < lastPartition.length; j++) {
 if (lastPartition[posOfLastNotOne] - 1 > lastPartition[j]) {
 System.arraycopy(lastPartition, 0, newPartition, 0, lastPartition.length);
 newPartition[posOfLastNotOne]--;
 newPartition[j]++;
 result.add(newPartition);
 break;
 }
 }
 }
 return result;
}

• Evgeni Nabokov: lastPartition.length is n, right? All partition arrays have the same size.
• Evgeni Nabokov: It seems to me that your logic is wrong. For n=6 it does not have [2,2,2], [3,3].

Answer 9

Here is my Rust implementation (inspired by Python Algorithms and Data Structures):

#[derive(Clone)]
struct PartitionIter {
 pub n: u32,
 partition: Vec<u32>,
 last_not_one_index: usize,
 started: bool,
 finished: bool
}
impl PartitionIter {
 pub fn new(n: u32) -> PartitionIter {
 PartitionIter {
 n,
 partition: Vec::with_capacity(n as usize),
 last_not_one_index: 0,
 started: false,
 finished: false,
 }
 }
}
impl Iterator for PartitionIter {
 type Item = Vec<u32>;
 fn next(&mut self) -> Option<Self::Item> {
 if self.finished {
 return None
 }
 if !self.started {
 self.partition.push(self.n);
 self.started = true;
 return Some(self.partition.clone());
 } else if self.n == 1 {
 return None;
 }
 if self.partition[self.last_not_one_index] == 2 {
 self.partition[self.last_not_one_index] = 1;
 self.partition.push(1);
 if self.last_not_one_index == 0 {
 self.finished = true;
 } else {
 self.last_not_one_index -= 1;
 }
 return Some(self.partition.clone())
 }
 let replacement = self.partition[self.last_not_one_index] - 1;
 let total_replaced = replacement + (self.partition.len() - self.last_not_one_index) as u32;
 let reps = total_replaced / replacement;
 let rest = total_replaced % replacement;
 self.partition.drain(self.last_not_one_index..);
 self.partition.extend_from_slice(&vec![replacement; reps as usize]);
 if rest > 0 {
 self.partition.push(rest);
 }
 self.last_not_one_index = self.partition.len() - (self.partition.last().cloned().unwrap() == 1) as usize - 1;
 Some(self.partition.clone())
 }
}