Integer partitioning and permutations of an array

This is a discussion on Integer partitioning and permutations of an array within the C Programming forums, part of the General Programming Boards category; I should start off by saying that this is my first time posting on this (or any) C programming forum. ...

  1. #1
    Registered User
    Join Date
    Sep 2011
    Posts
    2

    Lightbulb 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. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,488
    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. #3
    Registered User
    Join Date
    Sep 2011
    Posts
    2
    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. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.
    Last edited by Adak; 09-29-2011 at 08:44 PM.

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Partitioning array
    By baffleddreams in forum C Programming
    Replies: 4
    Last Post: 10-11-2010, 01:23 AM
  2. Partitioning array
    By baffleddreams in forum C Programming
    Replies: 2
    Last Post: 09-29-2010, 09:11 AM
  3. Integer partitioning
    By muhFah in forum C Programming
    Replies: 1
    Last Post: 09-18-2009, 10:37 AM
  4. Converting character array to integer array
    By quiet_forever in forum C++ Programming
    Replies: 5
    Last Post: 04-02-2007, 05:48 AM
  5. Partitioning....
    By Pyroteh in forum Tech Board
    Replies: 12
    Last Post: 07-09-2005, 04:32 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21