C recursive permutations

Question

i have been trying to complete figure out this part of my assignment to no avail for the past day, and require some help or guidance to help understand the problem.

so far i have this:

swap(int A, int B){
    int temp;
    temp = A;
    A = B;
    B = temp;
}


int max_array(int array[], int arraySize)
{
   int i, max=-32000;
   for (i=0; i<arraySize; i++)
   {
     if (array[i]>max)
     {
        max=array[i];
     }
   }
   printf("%d \n Max array: ", max)
   return(max);
}

int nextPermutation(int array[], int arraySize){
    int i;
    n = max_array(array, arraySize);
    if (int i; n == array[i] && i > 1; i++){
        swap(array[i], array[i-1]);
    }

    else if(int i; n == array[i]; i++){


    }
}

void main(){

    int intArray[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    //int intArray[10] = {1, 10, 3, 9, 8, 6, 7, 2, 4, 5};
    nextPermutation(intArray, 10);
    int i = 0;
    for(i = 0; i < 10; i++){
        printf("%d ",intArray[i]);
    }


}

But the question that i'm struggling to understand is "If a1,...,an is an arbitrary permutation (where a1,...,an are the numbers 1, 2, …, n in a probably different order) then the “next” permutation is produced by the following procedure: (i) If the maximal element of the array (which is n) is not the first element of the array, say n=ai , where i>1 , then to produce the "next" permutation you need to swap ai and ai−1 . (ii) If the maximal element of the array is in the first position, i.e. n=a1 , then to produce the “next” permutation to the permutation (a1,...,an) , first find the “next” permutation to the (n-1)-element permutation (a2,...,an ), and then append a1 to the end of thus obtained array of (n-1) elements."

so it needs to permutate every single possible combination with the array of 1,2,3,4,5,6,7,8,9,10 and then finish when it reaches this point "(n, …, 2, 1). And this is the only permutation that does not have the "next" permutation to it."

And the function int 'nextPermutation(int array[], int arraySize){' needs to stay the same.

Any help or tips will be excellent!

Answer 1

for swap sample

#include <stdio.h>

void swap(int* A, int* B){
    int wk;
    wk = *A;
    *A = *B;
    *B = wk;
}

int main(void){
    int array[] = { 1,2,3 };

    swap(&array[0], &array[2]);

    printf("array[0]=%d, array[2]=%d\n", array[0], array[2]);

   return 0;
}

Answer 2

There are some errors in your program,

swap() function will not affect the program as it doesn't use pass by reference.

max_array() should find the index of the maximum value, not the maximum value itself.

There is no recursion in your program as far as I can see.

main() should return int.

The program fragement given below might give you an idea,

    int ct=-1,n=10,temp[10]={0,0,0,0,0,0,0,0,0,0};
    int intArray[10]={1,2,3,4,5,6,7,8,9,10};

    permute(int k) 
    {     
            int i;     
            temp[k]=++ct;     
            if(ct==n-1)     
            {         
               for(i=0;i<n;i++)         
               {
                      printf("%d",intArray[temp[i]]);         
               }
               printf("\n");     
            }     
            for(i=0;i<n;i++)     
            {
               if(temp[i]==0)     
               {
                   permute(i);     
               }
            }
            ct--;     
            temp[k]=0;       
    } 

    int main() 
    {     
      permute(0);     
    }