number of permutations in c language

Question

hi friend When not in use the system to provide built-in function to achieve full array in c language. Such as: Please input n=3 123 132 213 231 312 321 Please input n=4 1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321 thanks.

Vulpes · Answer

Oops sorry Ken. In the nextperm fiunction I have this line in the wrong place: if (k == -1) return 0; It should be like this: int nextperm(int ia[] int n) { int i j k = -1 l; for(i = 0; i { if(ia[i] } if (k >= 0) { l = -1; for(i = 0; i { if(ia[k] } swap(&ia[k] &ia[l]); for(i = k + 1; i { j = n - i + k; if (i >= j) break; swap(&ia[i] &ia[j]); } } if (k == -1) return 0; // move above the lines which print out the array for(i = 0; i printf(
); return 1; }

Rohatash Kumar · Answer

Ken H Please check the below code: #include #include #include int lev=-1nval[50]a[50]; void main() { int ij; clrscr(); printf(Enter how many numbers?
); scanf(%d&n); printf(
Enter %d numbers:

n); for(i=0;i { val[i]=0; j=i+1; scanf(%d

&a[j]); } visit(0); getch(); } visit(int k) { int i; val[k]=++lev; if(lev==n) { for(i=0;i printf(%2da[val[i]]); printf( ); } for(i=0;i if(val[i]==0) visit(i); lev--; val[k]=0; }

Vulpes · Answer

Following your message here's a permutation generation program using a recursive algorithm: #include void swap(int *a int *b) { int temp = *a; *a = *b; *b = temp; } void print(int p[] int n) { int i; for(i = 0; i printf(
); } void permute(int p[] int k int n) { int j; if (k == n) { print(p n); } else { for(j = k; j { swap(&p[k] &p[j]); permute(p k + 1 n); swap(&p[j] &p[k]); } } } int main() { int i n; int p[10]; printf(Please input n (max 9) : ); scanf(%d &n); printf(
); for(i = 0; i { p[i] = i + 1; } permute(p 0 n); return 0; } For a description of how this algorithm works check out this link: www.cs.ucf.edu/~dmarino/ucf/cop3502/lec/Permutations.doc?

Vulpes · Answer

Consider first the case when i = k + 1. j will then be equal to n - (k + 1) + k which simplifies to n - 1 which is the index of the last element of the array. Consider next the case when i = k + 2. j will then be equal to n - (k + 2) + k which simplfies to n - 2 which is the index of the second last element of the array. So hopefully you can see now that the expression for j is giving us the indices we need to reverse the elements from k + 1 onwards. However your own expression which uses the auxiliary variable 'w' also works. So I'd go with that if you find it easier to understand.

Vulpes · Answer

That 'for' statement is reversing the elements of the array from index k + 1 to the end. To do that: 1. It swaps the element at index k + 1 with the one at n - 1 2. It swaps the element at index k + 2 with the one at n -2 3. And so on. So j is the index of the element to be swapped with the current value of i. When we reach the stage that i is equal to or greater than j then we know that no further swaps are necessary and we can just break from the 'for' loop. So all you've done is to get 'j' wrong - it should be n - i + k rather than n - 1 - i.

Ken H · Answer

Thank very much. I've mastered it.

Ken H · Answer

I can not understand this statement: j = n-i+k; I tried to replace it with w (i+k) the result looks like a right int w=1; for(i = k + 1; i { // j = n - i + k; j=n-w; if (i >= j) break; swap(&ia[i] &ia[j]); w++; }

Ken H · Answer

Thank you for your explanation.

Ken H · Answer

hi Vulpes Can you explain the role of the following iterations do(What does it do)? Thank for you. // Edited for(i = k + 1; i { j = n - i + k; if (i >= j) break; swap(&ia[i] &ia[j]); } I tried using the following method to replace the above but the results are not accurate. for(i=k+1;i { j=n-1-i; if(j swap (&ia[i] &ia[j]); }

Vulpes · Answer

Ken My solution is based on an old algorithm for generating successive permutations in lexicographic order discovered by the Indian mathematician Narayana Pandita in the 14th century. It's described in this Wikipedia article under the heading Generation in lexicographic order : http://en.wikipedia.org/wiki/Permutation

Ken H · Answer

hi Rohatash Kumar You can explain this 'visit' recursive procedure(step) do? Thank for you.

Ken H · Answer

hi Vulpes From the results seem to have an output is repeated. It runs as follows: Please input n (max 9) : 3 123 132 213 231 312 321 321 Press any key to continue

Vulpes · Answer

Ken If you want the permutations in lexographical order (as in your post) then try this: #include void swap(int *a int *b) { int temp = *a; *a = *b; *b = temp; } int nextperm(int ia[] int n) { int i j k = -1 l; for(i = 0; i { if(ia[i] } if (k >= 0) { l = -1; for(i = 0; i { if(ia[k] } swap(&ia[k] &ia[l]); for(i = k + 1; i { j = n - i + k; if (i >= j) break; swap(&ia[i] &ia[j]); } } if (k == -1) return 0; // EDITED see below for(i = 0; i printf(
); return 1; } int main() { int i n; int ia[10]; printf(Please input n (max 9) : ); scanf(%d &n); for(i = 0; i { ia[i] = i + 1; printf(%d ia[i]); } printf(
); while (nextperm(ia n)); return 0; }

Abhay Shanker · Answer

#include void swap(int *int*); void permute(void); int noofpermutations(); void display(void); int mnnooftermscount=0; int a[100]; void swap(int *p1int *p2) { int temp; temp = *p1; *p1 = *p2; *p2 = temp; } int noofpermutations() { int permutations=1x; for(x=1;x permutations=permutations*x; return permutations; } void display() { int x; for(x=0;x printf(%d a[x]); printf(
); count++; } void permute() { int xy; while(count { for(y=0;y { swap(&a[y]&a[y+1]); display(); } swap(&a[0]&a[1]); display(); for(y=noofterms-1;y>0;y–) { swap(&a[y]&a[y-1]); display(); } swap(&a[noofterms-1]&a[noofterms-2]); display(); } } main() { int x; printf(Enter no. of terms : ); scanf(%d&noofterms); printf(Enter the terms : ); for(x=0;x scanf(%d&a[x]); printf(
Permutations are : 
); permute(); printf(
Total Permutations : %dnoofpermutations()); return 0; }