# Thread: Integer partitioning and permutations of an array

1. ## Integer partitioning and permutations of an array

I should start off by saying that this is my first time posting on this (or any) C programming forum. I really don't like not being able to finish something by myself, but I am stuck and can't seem to come up with a solution. What my code is trying to accomplish is to take a single integer from the command line and find all integer partitions including mirrored partitions. For example if 4 were entered it should break into [1,3] [2,2] [3,1] [1,1,2] [1,2,1] [2,1,1] [1,1,1,1] and [4]. I have tried several different solutions, but every one I try either fails when larger integers are input (anything > 5 wouldn't output all partitions) or it prints several duplicate partitions. I've pretty much scraped everything and started from scratch. What I'm trying now is just storing every number that the input integer would break down to, into an array. So if 4 were entered, the array would hold [4,1,3,1,2,1,1]. That array is then sent to another function that, in theory, will form a second array. This array will start with any combination of 1 element that sums to the input number (n), and then print those elements. The function would then recurse and the new array would send all combinations of 2 elements that sum to n. Then any combination of 3 elements, so on until it gets to n elements (elements can be added with themselves), then the program will stop. I have two major issues though. First, I can't figure out how to get this new theoretical function of mine to work (as you can see in the code, there is really no progress made on that function). Second, this solution seems like it would take far too much processing time to be practical, so if you have any ideas that are completely different from my current idea, please let me know. Any help you all could give would be greatly appreciated. Thank so much, and without further ado, the code thus far...
Code:
```#include <stdio.h>
#include <stdlib.h>

void part(int, int[], int);
void printarray(int, int[]);
void permutations(int, int[], int[]);

int main (int argc, char *argv[])
{
int num = atoi(argv[1]);
int * out = calloc((num*2)-1, sizeof(int));
int * temp = calloc((num), sizeof(int));
int i = 1;
out[0] = num;

part(num, out, i);
permutations(num, out, temp);

free(out);
return 0;
}

void part (int n, int out[], int i)
{

out[i] = 1;
if ([n-1] = 0)
{
return;
}
else
{
out[i++] = [n--];
part(n, out, i);
}

}

void printarray(int n, int out[])
{
int x;
printf("[");
for(x = 0;x < n;x++)
{
if (out[x+1] < 1)
{
printf("%d]\n",out[x]);
}
else if(out[x] < 1)
{
x = n;
}
else
{
printf("%d ",out[x]);
}
}
}

void permutations(int n, int out[], int temp[])
{
int x;
int y;
int z;

for(x = 1; x < n; x++)
{```
Thanks so much!

2. I would probably approach this with a dynamic programming solution. If you're asked to find all the ways to make 5, you start with 1.
1. What are all the ways to make 1? Just 1.
2. What are all the ways to make 2? 1 + all the ways to make 1.
3. What are all the ways to make 3? 1 + all the ways to make 2, and 2 + all the ways to make 1.
4. What are all the ways to make 4? 1 + all the ways to make 3, and 2 + all the ways to make 2, and 3 + all the ways to make 1.
5. What are all the ways to make 5?

By "1 + all the ways to make 4", I mean you need a list of the combinations that make 4, and you need to add a 1 in each spot in each of those lists, and add it to the list of ways to make 5, making sure not to include a duplicate.

This isn't a trivial problem (apart from all the ways to make 1), but if you break it down into easy steps like that, and make sure you code small chunks, testing as you go, you should be alright. Hopefully that gets you going in the right direction.

3. Thanks for your response anduril. I never thought of the problem the way you suggested. I think I made some progress on my own solution though. My part subroutine is not work, however. If 4 is input, the output from the part subroutine is out = [4 1 1 1 2]. What I want it to do is put 4 into the array, then [1 3], then [1 2] then [1 1]. So the output array should look like [4 1 3 1 2 1 1]. My idea for the permutation subroutine is in comments at the bottom of the code. Again, thanks for all your help.
Code:
```#include <stdio.h>
#include <stdlib.h>

void part(int, int[], int);
void printarray(int, int[]);
void permutations(int, int[], int[]);

int main (int argc, char *argv[])
{
int num = atoi(argv[1]);
int * out = calloc((num*2)-1, sizeof(int));
int * temp = calloc((num), sizeof(int));
int i = 1;
out[0] = num;

part(num, out, i);
//permutations(num, out, temp);
printarray(num*2-1, out);

free(out);
return 0;
}

void part (int n, int out[], int i)
{

out[i] = 1;

out[++i] = n--;
printf("i = %d   n = %d\n",i,n);
if ((n-1) == 0)
{
return;
}
part(n, out, i);

}

void printarray(int n, int out[])
{
int x;
printf("[");
for(x = 0;x < n;x++)
{
if (out[x+1] < 1)
{
printf("%d]\n",out[x]);
}
else if(out[x] < 1)
{
x = n;
}
else
{
printf("%d ",out[x]);
}
}
}

/*void permutations(int n, int out[], int temp[])
{
int x;
int y;
int z;

for(x = 1; x < n; x++)
{

if out[] = [4131211]
start at 4, add to temp[].
if sum of temp[] vals == 4, inc counter, go to printarray
if not, and sum temp[] vals + next val > 4, skip value, go to next
if not, and sum temp[] vals + next val < 4, add value to temp[], go to next value

*/```

4. First thing I'd do is check with Wikipedia and see exactly what you do want. I'm unsure exactly what you want. Maybe all combinations from 0 to N, with repetitions?

I learned to do this with swaps and sorting and possibly increments, which allows the combinations to be output in sorted order. Obviously, the other way is to generate them out of sorted order, which is faster, but if the combinations aren't in sorted order, you can't tell at a glance if it's correct.

I've read Anduril's logic before, but that way never jelled into an efficient program for me.

Let me know what you're trying for, in a complete example of three or four numbers.

Edit: You're using this to make a larger part number? OK, that can use a completely different logic.

5. You need to really think about how you want it displayed.

Input: 4
Output: 4 = (3,1) or (2,2) or (1,3) or (112) or (211) or (1111)

OR

4 = (3(2(11)1 | 111 | 1(2(11))1), or ...

Quzah.