/*guys..I have implemented Jhonson trotter algorithm..u can
print permutations of 123..n. implement the same for strings!*/


#include<iostream.h>
#include<conio.h>
int min(int a[10],int n)
 {
   int i,m=1;
     for(i=2;i<=n;i++)
 {
     if(a[m]>a[i])
   m=i;
	  }
   return m;
	  }

void swap(int &a,int &b)
 {
   int t;
   t=a;
   a=b;
   b=t;
	  }
int main()
 {
   int i,j,k,n,flag=0,l,m;
   int d[100],a[100];
   clrscr();
   cout<<"\n\nenter n:\n\n";
   cin>>n;
      for(i=1;i<=n;i++)
   a[i]=i;
      for(i=1;i<=n;i++)
   d[i]=i-1;
   cout<<"\n\npermutations generated for integer 12...n
are:\n\n";
      for(i=1;i<=n;i++) //display the given no.
   cout<<a[i];
   cout<<"\t";
      do
 {
   flag=0;
   k=min(a,n);
      for(i=1;i<=n;i++)
 {
      if((a[i]>a[k])&&(d[i]!=0)&&(a[d[i]]<a[i])) //find
mobile integer.
   k=i;
	   }
      if(a[k]==1)
   break;
   l=d[k];   //copy of direction of mobile integer.
   m=a[k];   //copy of mobile integer.


      if(d[k]==k+1&&d[k+1]==k)        //swap directions.
 {

      if(d[k]==n)
 { d[k+1]=0;
   d[k]=k-1;
	  }

      else if(d[k+1]==1)
 {
   d[k]=0;
   d[k+1]=k+2;
	  }
      else
 { d[k]=k-1;
   d[k+1]=k+2;
	  }
	  }
      else if(d[k]==k-1&&d[k-1]==k)
 {
   d[k]=k+1;
   d[k-1]=k-2;
	  }
			   /*cout<<d[1]<<d[2]<<d[3]<<d[4];
			     cout<<"\t";
			     if u want to know directions of integers.
			     */
   swap(a[k],a[l]);  //swap mobile integer and integer it is
pointing to.
      for(i=1;i<=n;i++)
   cout<<a[i];          //display the number.
   cout<<"\t";
       for(i=1;i<=n;i++)  //reverse directions of integers
greater than
			 //mobile integer.
 {
       if(a[i]>m)
 {
       if(d[i]==0&&i==n)
   d[i]=i-1;
       else if(d[i]<i)
   d[i]=i+1;
       else if(d[i]>i)
   d[i]=i-1;
	     }
	     }
	for(i=1;i<n;i++) //check whether a mobile integer exist or not.
 {
       if(a[i]<a[i+1])
 {

       if(d[i+1]!=0)
   flag=1;
	     }

       else if(a[i]>a[i+1])
 {

       if(d[i]!=0)
   flag=1;
	     }
	     }
	     }
       while(flag==1);  //if no mobile
integer(flag=0)terminate the program.
   getch();
   return 0;
	     }