I don't like explaining things just code it., here's code below
#include#include #include int a[10]; int b[10]; void ResetArray(){ unsigned int i; for(i=0;i<10;i++){ a[i] = i; } } void swap_elements(unsigned int i,unsigned int j){ int temp; temp = a[i]; a[i] = a[j]; a[j] = temp; } /*b is the swap list*/ void InplacePermute(int *perm){ unsigned int i; for(i=0;i<10;i++){ if(perm[i] < i){ perm[i] = perm[perm[i]]; } if(a[i] < i){ perm[a[i]] = perm[i]; } swap_elements(i,perm[i]); } } void PrintPermutation(void){ unsigned int i; for(i=0;i<10;i++){ printf("%d ",a[i]); } } int main(){ int runs=10; unsigned int i; do{ ResetArray(); printf("Please enter the permutation of size 10, 10 unique digits from 0-9\n"); for(i=0;i<10;i++){ if(scanf("%d",&b[i])<=0){ break; } assert(b[i] >=0 && b[i] <=10); } if(i<10){ break; } InplacePermute(b); printf("The permutation is::"); PrintPermutation(); }while(1); }
The following are testcases
7 3 2 1 4 8 9 0 5 6 8 9 1 2 5 6 7 3 4 0 1 2 3 4 5 6 7 8 0 9 1 3 4 8 9 0 7 6 5 2Well this week has been a little productive, got the space for http://phaedrus.sourceforge.net a library of randomized algorithms
Have Fun.... Vamsi.
2 comments:
I am bala nagi reddy..hope you remember me..can you give description like that the algorithm does..
I mean what is the output and its significance..
Can you write a small code to permute a list of numbers?
I want both recursive and iterative..
hi bala,
As indicated above you need to permute a set of numbers 1...n in the array in this case 1...10 according to the permutation given as input.
as a proof of concept the algorithm works on 10 numbers 1 to 10 and takes input a permutation like '7 3 2 1 4 8 9 0 5 6' and arranges the input array in that order without any extra space and in O(n) time see InplacePermute for the main algorithms code.
Post a Comment