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).

Kreg

This can help: numericana.com/answer/numbers.htm#partitions – Denouement

@DavidRF Thanks, but the link calculates the number of partitions (not the actual partitions) and that too with repeats allowed. A more accurate description would be oeis.org/A000009 but it still does not help me to generate those partitions. – Kreg

possible duplicate of Project Euler 76 - List All Partitions For a Given Number – Hairline

@Hairline This question is different because I additionally require each number in a partition to be distinct. So something like n 1's is not allowed. – Kreg

Generate set of partition for a set of elements (in particular numbers) is a classical problem of backtracking. – Rihana

For future reference, Patrick87's answer makes things very easy to understand. – Kreg

Answer 1

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);
    }
}

Handgun

Thank you very much! This seems to work great! I'll try to understand it and test it out. – Kreg

Answer 2

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;
}

Seiber

Please, please, please don't write code like ((tot += *ptr++ = cur++) < part). It's super inscrutable and the condensed code is a false savings in terms of readability and maintainability. (Note that there's a whole follow-up question based on trying to understand this. – Marji

@Seiber could you help me on #49453104 – Firry

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

California

Thanks! The number of partitions with repeats grows much faster than the number of partitions without repeats. I was hoping to avoid the substantially extra work. – Kreg

@Kreg Please see my edit. This should solve your problem without generating invalid answers. Basically, this solves the problem "find all partitions of a number not containing any of a set of elements". Your problem is reducible to this problem; call the given algorithm with alreadySeen = {}. – California

Thank you! I was trying to understand it, and this looks good. I think it may generate the same partition set multiple times, but the UNION operator with results should take care of it. I'll give it a try. – Kreg

@Kreg Indeed, it might. Of course, this problem can be overcome by only looping over numbers greater than or equal to the last number. In fact, you can get rid of the whole "alreadySeen" business and solve the following problem: find all partitions consisting of numbers strictly greater than a given number". Your problem is reducible to that one, as well; call the function with 0 as the "must be greater than this" argument. Then, change the for loop to start at mustBeGreaterThan + 1, instead of at 1. – California

Yes, after reading your previous pseudo code, I was also thinking on similar lines. Thanks for confirming and providing an updated pseudo-code! This looks much simpler, nicer and should be faster. – Kreg

This solution can be hugely inefficient in some cases. For example, the number of partitions of the number 30 with no constraint on replication is 5507, but with a replication constraint, it is 263. Since it is fairly easy to write the code that does it with out replication, just do the job right in the first place. – Zama

@woodchips I give a few different ways of doing this in my answer, with varying degrees of efficiency. – California

Can this be optimized if only we need is to count how many options there are? – Jair

Answer 4

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.

Uriah

I believe that at step i, he could iterate from i+1 to remainder-i; all numbers above remainder-i would have been already considered, and fall into a duplicate partition. – Fairy

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;
}

Tinderbox