Sunday, August 15, 2010

Simple Permutations Algorithm

Today i decided to write my own algorithm for generating permutations for a given set of integers. One of the ideas that hit my mind was using array cyclic shift.

The algorithm is as follows:_

for 1 2 3 4
it would be like this
1 2 3 4 --->2341-->3412-->4123

For each set of the above 4 sets, the element with index 0 is fixed and the rest of the array is shifted. In this manner:


For each one of the above 3 sets, the elements with indexes 0 and 1 are fixed  and the rest of the array is shifted.
In this manner:


Here is the code for my algorithm

void permutation(int X[],int size,int level)
if(level==size-1) return;
int* A=(int*)malloc(size*sizeof(int));
int i=0;
while(i<(size-level)) { shift(&A[level],size-level,i); if(!level) print(A,size); else if(i) print(A,size); permutation(A,size,level+1); i++; memcpy(A,X,size*sizeof(int)); } free(A); return; }

Any suggestions are very welcome.  You can find an example here.

No comments:

Post a Comment