hi all , i am trying for implementing code for permutation in place i have written code after reading some research paper on that topic but i am getting some difficulty for understanding cycle leader and cycle structure in permutation task is rearrange the array element without using other array i m showing my code here i am trying to understand one function pi() which is mean there // permutation in oracle but i did not get actual meaning and did not getting correct answer plase help me for that problem as soon as possible. i am just takink my imagination in definition of pi() fun. may be it wrong.. ...
CODE
#include<iostream.h>
#include<conio.h>
int n=4;
int a[4]={1,2,3,4};
int *ar[4]; /* the array to be permuted */
*ar[] = &a[];
void exchange (int i ,int j)
{
int temp=*ar[i];
*ar[i]=*ar[j];
*ar[j]=temp;
}
int pi(int x) /* permutation as oracle */
{
switch(x)
{
case 0: return 3;
break;
case 1: return 1;
break;
case 2: return 2;
break;
case 3: return 0;
break;
default : cout<<"no exist pos.";
break;
}
}
int IsLeader(int i);
void PermuteCycle(int i)
{
int j=i; /* loop variable */
do
{
j=pi(j); /* follow cycle */
exchange(i,j); /* exchange a[i] and a[j] */
}
while (j!=i);
}
void main(void)
{
clrscr();
int i,ret; /* loop variable */
for(i=0;i<4;i++)
cout<<" "<<a[i];
cout<<endl;
for(i=0;i<n;i++)
{ ret=IsLeader(i);
if(ret==1)
PermuteCycle(i);
}
for(i=0;i<4;i++)
cout<<" "<<a[i];
cout<<endl;
getch();
}
int TestHypo(int j,int i)
{
return i<=j;
}
int IsLeader(int i)
{
int j=i,ret; /* loop variable */
int flag=1; /* assume i is leader */
do
{
j=pi(j); /* follow cycle */
ret=TestHypo(j,i);
if(flag==ret)
{ //flag=0;
break;
}
/* until assumption turns out false */
}
while (j!=i); /* or cycle is completely traversed */
return flag;
}
~Added code tags
-jjsaw5
| 