Sunday, February 18, 2007

Algorithm for Permuting in place

Problem: Given a set of numbers S = 1...n and a permutation PI(S), how can you rearrange elements in S in O(n) time with no extra space.

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 2
Well 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:

Anonymous said...

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..

Vamsi Kundeti said...

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.