Thread: permutation of a 2D integer array.

  1. #1
    Registered User
    Join Date
    Jun 2012
    Posts
    4

    Post permutation of a 2D integer array.

    I need to get find the maximum possible sum of a 2D array, but can only use one number per row/column (similar to the Hungarian Method). I've been working on the code for quite some time, but I haven't gotten far. I'm fairly new to programming, so the explanations online are far above my knowledge of the C language.
    I don't really have much, but here it is:

    Code:
    
    int permute(int mmin[10][10], int size){
    int q, total=0, sum=0;
    
    
    
    
       for(q=size;q>=0;q--){
    
    
    
    
        mmin=swap(mmin, size, q);
        sum=mmin[q][q];
    
    
        sum+=permute(mmin, q-1);
    
    
    
    
        mmin=swap(mmin, q, size);
    printf("\n");
    
    
    }
    
    
    return sum;
    }
    int swap(int mmin[10][10], int j, int k){
     int i, temp;
     for(i=0;i<=k;i++){
         printf("swapping [%d][%d]=%d with [%d][%d]=%d\n", i, j, mmin[i][j], i, k, mmin[i][k]);
         temp=mmin[i][j];
         mmin[i][j]=mmin[i][k];
         mmin[i][k]=temp;
     }
     return mmin;
    }
    I know, it's a mess. The program adds the diagonal numbers together ([0][0]+[1][1]+[2][2]+...) but the swap is giving me trouble. I only learned how to print permutations of a word, not of sums of 2D arrays. any help?
    Thanks in advance!

    I also know that i need an if statement to stop all of the swaps, but I'm not sure where yet...
    Last edited by zwolf2190; 06-15-2012 at 12:12 PM.

  2. #2
    Registered User
    Join Date
    Jun 2012
    Posts
    4
    I changed my swap to
    Code:
    int swap(int mmin[10][10], int j, int k, int realsize){ int i, temp;
     for(i=0;i<=realsize;i++){
         printf("swapping [%d][%d]=%d with [%d][%d]=%d\n", i, j, mmin[i][j], i, k, mmin[i][k]);
         temp=mmin[i][j];
         mmin[i][j]=mmin[i][k];
         mmin[i][k]=temp;
     }
    with realsize keeping track of the amount of array spots.
    the for loops have <= because size and realsize come in as -1 of the array size.
    it's getting some permutations, but not all.
    example:
    when the array is:
    4 6 4
    6 5 5
    5 9 3
    the diagonal is 3+5+4
    and the permutations are 354, 366, 954, 964, 554, 556.
    the new swap is making it go 354, 366, 954, (skip 964), 554, (skip 556)

  3. #3
    Registered User
    Join Date
    Jun 2012
    Posts
    4
    I've got some conditions that i forgot to mention: the largest size is a 2d array of size 10 and there are the same amount of columns as there are rows.
    I'm not sure how, but I've gotten it to print out every permutation with some duplicates. here's the code:
    Code:
    int permute(int mmin[10][10], int mdiff[10][10], int size, int realsize){
    int q, total=0, sum=0, i, j;
       for(q=size;q>=0;q--){
    
    
        mmin=swap(mmin, size, q, realsize);
        sum=mmin[q][q];
    
    
        sum+=permute(mmin, mdiff, size-1, realsize);
    for(i=0;i<=realsize;i++){
        for(j=0;j<=realsize;j++){
            printf("%d", mmin[i][j]);
        }
        printf("\n");
    }
    if(sum>total)
    total=sum;
    //printf("sum is %d\n", sum);
        mmin=swapback(mmin, q, size, realsize);
    printf("\n");
    
    
    }
    
    
    return total;
    }
    int swap(int mmin[10][10], int j, int k, int realsize){
    
    
     int i, temp;
     for(i=0;i<=realsize;i++){
         printf("swapping [%d][%d]=%d with [%d][%d]=%d\n", i, j, mmin[i][j], i, k, mmin[i][k]);
         temp=mmin[i][j];
         mmin[i][j]=mmin[i][k];
         mmin[i][k]=temp;
     }
     return mmin;
    }
    int swapback(int mmin[10][10], int j, int k, int realsize){
     int i, temp;
     for(i=0;i<=realsize;i++){
         printf("swapping back [%d][%d]=%d with [%d][%d]=%d\n", i, j, mmin[i][j], i, k, mmin[i][k]);
         temp=mmin[i][j];
         mmin[i][j]=mmin[i][k];
         mmin[i][k]=temp;
     }
     return mmin;
    }
    ignore mdiff. swapback is different only because i wanted it to print "swapping back..." instead of just "swapping" for tracing purposes. The sum doesn't seem to work. i'm guessing it has to do with "sum+=permute(...)" and all of the swapping.

  4. #4
    Registered User
    Join Date
    Jun 2012
    Posts
    4
    OH. Silly me for initializing total to zero every time...
    Like how i'm talking to myself too?

  5. #5
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Although you mention the "Hungarian method", which is polynomial (n cubed), you are apparently attempting to implement an exponential (brute force) method. I assume it's the brute force method you want.

    I don't understand why you're swapping columns of the 2D array around. It's not necessary. You should probably leave the 2D matrix alone and permute a 1D array of column indicies. Each entry in the 1D array will indicate a column in the respective row. So, e.g., if it contains 2,1,3,0 it refers to (0,2), (1,1), (2,3), (3,0) (where the first number is the row of the matrix and the second is the column).

    So you want to test all permutations of the numbers 0, 1, 2, ..., size - 1. If adding the indicated elements gives a greater total than the saved total, save the new total and a copy of the column array. Once you've gone through all the permutations, just print out the saved total and column array.

    Also, C++ has the std::next_permutation function in <algorithm> to generate permutations. See next_permutation - C++ Reference for an example.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Complex permutation of elements of an array
    By drew99 in forum C Programming
    Replies: 3
    Last Post: 10-25-2011, 12:10 PM
  2. Permutation of an array of strings
    By JonathanS in forum C Programming
    Replies: 5
    Last Post: 10-19-2011, 06:01 PM
  3. Converting character array to integer array
    By quiet_forever in forum C++ Programming
    Replies: 5
    Last Post: 04-02-2007, 05:48 AM
  4. Sorting: Getting permutation index array
    By flyvholm in forum C Programming
    Replies: 2
    Last Post: 09-20-2006, 07:07 PM
  5. INT ARRAY Permutation!
    By arthur5005 in forum C++ Programming
    Replies: 2
    Last Post: 10-21-2002, 05:30 AM

Tags for this Thread