Wednesday, October 21, 2009

Simple permutation algorithm (lexicographic, i.e output sorted)

Here's a small recursive permutation algorithm in C which returns the permutations in ascending order.
#include <stdlib.h>
#include <stdio.h>

#define MAX 100 /*max number of values to permute*/


int array[MAX];/*value array*/
int visited[MAX];/*array to set a "visit" flag, to see if a value has been previously visited*/
int size;/*number of values to permute*/
int output[MAX];/*output array(contains output values set by permute())*/
int k=0;/*k contains number of visited values at any particular time during permute()*/

int print_output()
{
/*print output array*/
int i;
for(i=0;i<size;i++)
printf("%d ",output[i]);
printf("\n");

}

int permute()
{
/*recursive permutation function*/
int i;
if(k==size)/*if number of visited values reaches "size", it means that we've got a particular combination to output, so we print it*/
{
print_output();
return 0;
}
for(i=0;i<size;i++){
if(visited[i]==0){ /*remove this line(and it's bottom bracket) to obtain combinations too(e.g 1111,1223,etc.)*/
visited[i]=1; /*value visited so set "visit flag"*/
output[k]=array[i]; /*add value to output array*/
k++; /*increase number of visited values*/
permute(); /*recall the same function until k reaches size*/
visited[i]=0; /*already processed, remove "visit" flag*/
k--; /*decrease number of visited values, as we're "unvisiting" previous value*/
}
}

}

int init()
{
/*initialize the array of values to 1,2,3,4,..(u can use other values too which will be permuted, from user input for example)*/
int i;
for(i=1;i<=size;i++)
array[i-1]=i;
}

int main()
{
printf("Enter number of values to permute: ");
scanf("%d",&size); /*input size*/
init();/*initialize the array of values to 1,2,3,4,..(u can use other values too which will be permuted, from user input for example)*/
permute(); /*permute the values in the array(output function implemented inside)*/
return 0;
}



Compile with: gcc permutation.c -o permutation

2 comments:

  1. thanks for sharing this site. you can download lots of ebook from here

    http://feboook.blogspot.com

    ReplyDelete