Generating all distinct partitions of a number

Question

I am trying to write a C code to generate all possible partitions (into 2 or more parts) with distinct elements of a given number. The sum of all the numbers of a given partition should be equal to the given number. For example, for input n = 6, all possible partitions having 2 or more elements with distinct elements are:

• 1, 5
• 1, 2, 3
• 2, 4

I think a recursive approach should work, but I am unable to take care of the added constraint of distinct elements. A pseudo code or a sample code in C/C++/Java would be greatly appreciated.

Thanks!

Edit: If it makes things easier, I can ignore the restriction of the partitions having atleast 2 elements. This will allow the number itself to be added to the list (eg, 6 itself will be a trivial but valid partition).

Answer 1

You don't need recursion at all. The list of numbers is essentially a stack, and by iterating in order you ensure no duplicates.

Here's a version which shows what I mean (you tagged this C, so I wrote it in C. In C++ you could use a dynamic container with push and pop, and tidy this up considerably).

#include <stdio.h>
#include <stdlib.h>
void partition(int part)
{
int *parts;
int *ptr;
int i;
int idx = 0;
int tot = 0;
int cur = 1;
int max = 1;
 while((max * (max + 1)) / 2 <= part) max++;
 ptr = parts = malloc(sizeof(int) * max);
 for(;;) {
 if((tot += *ptr++ = cur++) < part) continue;
 if(tot == part) {
 for(i = 0 ; i < ptr-parts ; i++) {printf("%d ",parts[i]);}
 printf("\n");
 }
 do {
 if(ptr == parts) {free(parts); return;}
 tot -= cur = *--ptr;
 } while(++cur + tot > part);
 }
}
int main(int argc, char* argv[])
{
 partition(6);
 return 0;
}

Answer 2

What you're trying to do doesn't make a lot of sense to me but here's how I would approach it.

First, I'd create a loop that iterates i from 1 to n - 1. In the first loop, you could add the partition 1, i. Then I'd go recursive using the value in i to get all the sub-partitions that can also be added to 1.

And then continue to 2, and so on.

Answer 3

First, write a recursive algorithm that returns all partitions, including those that contain repeats.

Second, write an algorithm that eliminates partitions that contain duplicate elements.

EDIT:

You can avoid results with duplicates by avoiding making recursive calls for already-seen numbers. Pseudocode:

Partitions(n, alreadySeen)
 1. if n = 0 then return {[]}
 2. else then
 3. results = {}
 4. for i = 1 to n do
 5. if i in alreadySeen then continue
 6. else then
 7. subresults = Partitions(n - i, alreadySeen UNION {i})
 8. for subresult in subresults do
 9. results = results UNION {[i] APPEND subresult}
10. return results

EDIT:

You can also avoid generating the same result more than once. Do this by modifying the range of the loop, so that you only add new elements in a monotonically increasing fashion:

Partitions(n, mustBeGreaterThan)
1. if n = 0 then return {[]}
2. else then
3. results = {}
4. for i = (mustBeGreaterThan + 1) to n do
5. subresults = Partitions(n - i, i)
6. for subresult in subresults do
7. results = results UNION {[i] APPEND subresult}
8. return results

Answer 4

I sketched this solution (it can be beautified and optimized) that shouldn't generate duplicates:

void partitions(int target, int curr, int* array, int idx)
{
 if (curr + array[idx] == target)
 {
 for (int i=0; i <= idx; i++)
 cout << array[i] << " ";
 cout << endl; 
 return;
 }
 else if (curr + array[idx] > target)
 {
 return;
 }
 else
 {
 for(int i = array[idx]+1; i < target; i++)
 {
 array[idx+1] = i;
 partitions(target, curr + array[idx], array, idx+1);
 }
 }
}
int main(){
 int array[100];
 int N = 6;
 for(int i = 1; i < N; i++)
 {
 array[0] = i;
 partitions(N, 0, array, 0);
 }
}

Answer 5

It is another solution that is based on an iterative algorithm. It is much faster than @imreal's algorithm and marginally faster than @JasonD's algorithm.

Time needed to compute n = 100

$ time ./randy > /dev/null
./randy > /dev/null 0.39s user 0.00s system 99% cpu 0.393 total
$ time ./jasond > /dev/null
./jasond > /dev/null 0.43s user 0.00s system 99% cpu 0.438 total
$ time ./imreal > /dev/null
./imreal > /dev/null 3.28s user 0.13s system 99% cpu 3.435 total

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int next_partition(int *a, int* kp) {
 int k = *kp;
 int i, t, b;
 if (k == 1) return 0;
 if (a[k - 1] - a[k - 2] > 2) {
 b = a[k - 2] + 1;
 a[k - 2] = b;
 t = a[k - 1] - 1;
 i = k - 1;
 while (t >= 2*b + 3) {
 b += 1;
 a[i] = b;
 t -= b;
 i += 1;
 }
 a[i] = t;
 k = i + 1;
 } else {
 a[k - 2] = a[k - 2] + a[k - 1];
 a[k - 1] = 0;
 k = k - 1;
 }
 *kp = k;
 return 1;
}
int main(int argc, char* argv[])
{
 int n = 100;
 int m = floor(0.5 * (sqrt(8*n + 1) - 1));
 int i, k;
 int *a;
 a = malloc(m * sizeof(int));
 k = m;
 for (i = 0; i < m - 1; i++) {
 a[i] = i + 1;
 }
 a[m - 1] = n - m*(m-1)/2;
 for (i = 0; i < k; i++) printf("%d ", a[i]);
 printf("\n");
 while (next_partition(a, &k)) {
 for (i = 0; i < k; i++) printf("%d ", a[i]);
 printf("\n");
 }
 free(a);
 return 0;
}