C program Please help me in my question 2as we noticed in t

C program: Please help me in my question

-----------------------------------------------------------------------------------------------------------

2)as we noticed, in this code

#include <stdio.h>

#define LEN 4

void swap(int array[], int i, int j);

void permute(int array[], int k, int n);

int main() {

int array[LEN], i;

for (i = 0; i < LEN; i++)

array[i] = i + 1;

permute(array, 0, LEN);

}

void permute(int array[], int k, int n) {

int i;

if ( k>= n-1) {

for (i = 0; i < n; i++)

printf(\"%d \", array[i]);

printf(\"\ \");

}

else {

for (i = k; i < n; i++) {

swap(array, k, i);

permute(array,k+1 ,n );

swap(array, k, i);

} }

}

/* Function swaps swaps the elements array[i] and array[j] */

void swap(int array[], int i, int j) {

int temp = array[i];

array[i] = array[j];

  array[j] = temp;

}

The generated permutations are not lexicographically ordered. For example, for n = 4 the generated permutations were:

1 2 3 4

1 2 4 3

1 3 2 4

1 3 4 2

1 4 3 2

. . .

-----------------------------------------------------------------------------------------------------------

while the lexicographically ordered permutations would be:

1 2 3 4

1 2 4 3

1 3 2 4

1 3 4 2

1 4 2 3

. . .

If you are not familiar with lexicographic order, we can define it in the following way: We compare two sequences of numbers (or letters, or other comparable elements), from the start and keep doing it while the sequence elements are equal. We come across the first elements that are different, we decide that sequences compare in the same way as those two elements. In the above example, when we compare sequences (1,4,3,2) and (1,4,2,3), we see that the sequences differ first time at the third position, and the sequence with 2 at the third position should come before the sequence with 3 at third position; i.e., the order should be (1,4,2,3) and then (1,4,3,2).

Your task is to write the C program that generates permutations in the lexicographically ordered way. The program must have two modes of operation, in one they the program must produce all permutations, and in other it must produce only the permutation that comes at certain position in the permutations list.

Input:

Each line of input contains two integers m and n. The input ends with integers 0 and 0. Other than the final two numbers, n is always the positive integer. If the first number m is 0, you program must print all permutations of numbers 1, 2, ..., n in the lexicographic order. If the number m is positive, then your program must print only the m’th permutation of numbers 1, 2, . . . , n in the lexicographic order. If the number m is so large that you run out of permutation, your program should not print anything.

Output:

For each par of numbers m and n in the input, your program should first produce the line that looks like: m=m n=n

This must be produced even for the final ‘0 0’ line. After that, if m = 0 and n > 0 the program must produce all permutations as specified, one permutation per line; or if m > 0 only the specified permutation, or no permutations at all if m is larger than the number of permutations.

Sample Input: 0 3 3 4 5 4 30 4 Sample Output: m=0 n-3 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 m=3 n=4 1 3 2 4 m=4 n=4 1 3 42 m=5 n=4 1 4 2 3 m=30 n=4 m=0 n=0

Solution

#include <stdio.h>

void swap(int array[], int i, int j);
void permute(int array[], int n, int m );

int main() {
   int m,n;
   while(1){
       scanf(\"%d %d\",&m,&n);
       int array[n];
       int i;
       for (i = 0; i < n; i++){ array[i] = i + 1; }
       if( m==0 && n==0 ){
           break;
       }
       permute(array,n,m);
   }
   return 0;
}

int compareFxn(const void * a, const void * b){   return ( *(int*)a - *(int*)b ); }

void permute( int array[], int n , int m){
   printf(\"m=%d n=%d\ \", m,n);
   qsort( array, n, sizeof(array[0]), compareFxn );
   int permNo = 1;
   while(1){
       int i;
       if( m==0 || (m != 0 && permNo == m)){
           i = 0;
           printf(\" \");
           for(; i < n; i++){ printf(\"%d \", array[i]); }
           printf(\"\ \");
       }

       for(i=n-2; i>=0; i--){
           if(array[i]<array[i+1]){
               break;
           }
       }
       if( i == -1 ){ break; }
       int index = i+1;
       int j = i+2;
       for( ; j<= n-1; j++){
           if( array[j]> array[i] && (array[j] < array[index])){
               index = j;
           }
       }
       swap( array,i,index );
       qsort( array+i+1, n-i-1, sizeof(array[0]) , compareFxn);
       permNo++;
   }  
}

/* Function swaps swaps the elements array[i] and array[j] */
void swap(int array[], int i, int j) {
   int temp = array[i];
   array[i] = array[j];
   array[j] = temp;
}