Generating all distinct partitions of a number

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

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

Generate all unique partitions of an integer, Given a positive integer n, generate all possible unique ways to represent n as sum of positive integers. Examples: Input: n = 2 Output: 2 1 1 Input:� Such a partition is called a partition with distinct parts. If we count the partitions of 8 with distinct parts, we also obtain 6: 8; 7 + 1; 6 + 2; 5 + 3; 5 + 2 + 1; 4 + 3 + 1; This is a general property. For each positive number, the number of partitions with odd parts equals the number of partitions with distinct parts, denoted by q(n).

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.

Generate all unique partitions of an integer, The idea is simple and is kind of same approach as used here. We have to move recursively from n to 1 and keep on appending the numbers used to form sum in the array. When the sum becomes equal to n then we print the array and return. Generate all unique partitions of an integer; Find ways an Integer can be expressed as sum of n-th power of unique natural numbers; Given a string, print all possible palindromic partitions; Sum of elements of all partitions of number such that no element is less than K

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
```

Partition (number theory), Among the 22 partitions of the number 8, there are 6 that contain only odd For every type of restricted partition there is a The generating function for q(n) ( partitions into distinct parts) is given by. Ex 3.3.2 Find the generating function for the number of partitions of an integer into distinct odd parts. Find the number of such partitions of 20. Ex 3.3.3 Find the generating function for the number of partitions of an integer into distinct even parts. Find the number of such partitions of 30. Ex 3.3.4 Find the number of partitions of 25 into

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

3.3 Partitions of Integers, There is no simple formula for pn, but it is not hard to find a generating function for in all possible ways, with the further condition that we only pick a finite number of Let pd(n) be the number of partitions of n into distinct parts; let po(n) be the� This way we can generate the all the required unique partitions from a given number. The complexity of the above approach will be O(c) as there are c unique partitions and we need to generate all the c partitions. Here c can take a maximum value of 2^n as there are a total of 2^n possible partitions.

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

[PDF] Fast Algorithms for Generating Integer Partitions, Thus two partitions of an integer n are distinct if they differ with respect to generating all the partitions of an integer, or sometimes just those satisfying various. Notes on partitions and their generating functions 1. Partitions of n. In these notes we are concerned with partitions of a number n, as opposed to partitions of a set. A partition of nis a combination (unordered, with repetitions allowed) of positive integers, called the parts, that add up to n.

Number of unique partitions of an integer, the first is the naive approach which uses brute force method to generate all possible compositions and separate the unique compositions. This takes O((N^N )log� The order of the integers in the sum "does not matter": that is, two expressions that contain the same integers in a different order are considered to be the same partition. The number of different partitions of n n n is denoted p (n) p(n) p (n). This function is called the partition function. The partitions of 5 5 5 are as follows:

Generating function of the number of integer partitions of \$n\$ into all , Let pd(n) denote the number of integer partitions of n into all distinct parts. I am given the following equation, but I can't figure out why it holds: ∑� In a similar way as we have seen in the previous propositions, we can show that the generating function for the number of partitions of n, into odd parts. Capital Po(q), which is Po(n) times q to the power n, for n greater than or equal to 0, is equal to the product of infinitely many geometric series, with common ratios q, q to the third, q to

• @mbeckish 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.
• 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.
• 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.