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

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)

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.

OH. Silly me for initializing total to zero every time...
Like how i'm talking to myself too?

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.