p_2.c

Friday, 14 January 2011 06:01
// To compute number of cycles for a permutation to map onto itself


#include 



#define SIZE 20

#define MAX 200



int f(int* p)

{

 int i,j,orig,tmp;

 int cnt[SIZE],flag[SIZE];  

 int sim[MAX];

 int global_len=1;

 int gcd,t,n1,n2;



 for(i=0 ; i  flag[SIZE]=0;



 for(i=0 ; i {

  if(flag[i]!=1 && p[i]==i)

  {

   printf("Checking %d #######\n",i);

   cnt[i]=1;

   flag[i]=1;

   printf("Length : %d \n",cnt[i]);

   continue;

  }

  else if(flag[i]!=1)

  {

   printf("Checking %d #######\n",i);



   orig=i;

   tmp=p[i];

   cnt[i]=1;

   j=0;

   sim[j++]=tmp;

   flag[tmp]=1; 

   

   while(tmp!=orig)

   {

    tmp=p[tmp];

    sim[j++]=tmp;

    cnt[i]++;

   }

   

   flag[i]=1;

   printf("Length : %d\n",cnt[i]);



   printf("Similar : %d ",sim[0]);

   while(--j && j>=0)

   { 

     flag[sim[j]]=1;

     cnt[sim[j]]=cnt[i];  

     printf("%d ",sim[j]);

   }



   n1= global_len;

   n2= cnt[i];

 

   if(n1>n2)

   {

    n1=n1+n2; n2=n1-n2; n1=n1-n2;

   }

   while(n2%n1 != 0)

   {

     t=n1; n1=n2%n1; n2=t;

   }

   gcd=n1;

   global_len=global_len*(cnt[i]/gcd);     

  

   printf("\n");

  }

 }

  

 return global_len;

}



int main()

{

 int i,j,orig,tmp; 

 int p[SIZE]={1,2,0,4,9,5,7,8,19,6,11,3,13,14,18,16,17,15,12,10}; 



 printf("Cycle length : %d\n",f(p));



 return 0;

}