/*  
Chad Brewbaker
2-25-2003

This program outputs the distance of every possible hamiltonian cycle in a graph from the standard form.

Standard form is 1-2-3-4-5-6...-N-1

Distance is defined as the number of vertex transpositions needed to get from one cycle to another. Example


13245 takes one transposition (32)->(23)  to get to normal form.


Also 12345 is the same as 54321 (Flips) and 12345 is the same as 23451 (rotations).


Trivaily there are n!/(2n) possible hamiltionian cycles in a given graph.



***TODO***
-Add permutation code to enumerate all cycles...


-Simplify length by starting every array with 0. Should reduce things by a factor of n.

*/


#include <iostream.h>


int cycleList[10000][10];
int stdList[1000][10];
int goodArr[10];

/*does a dfs search as to which vertices should be swaped in order to achive a normal form*/
int DFSPass(int cycleIndex, int cycleLength,int standardIndex)
{
  int i,j,k;
  int temp=0;
  int tempMax,max;
  int goodTmp1,goodTmp2;
  tempMax=max=0;
  
  /*Check to see if we are finished*/
  for(i=0;i<cycleLength;i++)
    temp+=goodArr[i];
  if(temp==cycleLength)
    return 0;
  for(i=0;i<cycleLength-1;i++)
    {
      for(j=i;j<cycleLength;j++)
	{
	  if(!( goodArr[i]||goodArr[j]))
	    {  
	      /*ASSUMPTION: At each transpose at least one of the verticies must fall into the right place*/
	      if(
		 stdList[standardIndex][i]==cycleList[cycleIndex][j]
		 || stdList[standardIndex][j]==cycleList[cycleIndex][i])
		{
		  temp=cycleList[cycleIndex][i];
		  cycleList[cycleIndex][i]=cycleList[cycleIndex][j];
		  cycleList[cycleIndex][j]=temp;
		  goodTmp1=goodArr[i];
		  if(stdList[standardIndex][i]==cycleList[cycleIndex][i])
		    goodArr[i]=1;
		  goodTmp2=goodArr[j];
		  if(stdList[standardIndex][j]==cycleList[cycleIndex][j])
		    goodArr[j]=1;
		  tempMin= DFSPass(cycleIndex,cycleLength,standardIndex)+1;
		  if(tempMin<Min)
		    Min=tempMin;
		  //Cleanup afer ourselves
		  temp=cycleList[cycleIndex][i];
		  cycleList[cycleIndex][i]=cycleList[cycleIndex][j];
		  cycleList[cycleIndex][j]=temp;
		  goodArr[i]=goodTmp1;
		  goodArr[j]=goodTmp2;
		}
	    }
	}      
    }
  return Min;
}



/* Swaps two verticies according to some standard form if they should be swapped*/
/*It returns the number of swaps performed*/
int  swapPass(int cycleIndex, int cycleLength, int standardIndex)
{
  int i,j,k;
  int total=0;
  int done=0;
  int temp;
  
  //do an nxn pass checking if two verticies can be swaped

  while(!done)
    {
      done=1;
      for(i=0;i<cycleLength-1;i++)
	{
	  for(j=i+1;j<cycleLength;j++);
	  {
	    if(cycleList[cycleIndex][i]==stdList[standardIndex][j]
	       &&
	       cycleList[cycleIndex][j]==stdList[standardIndex][i])
	      {
		temp=cycleList[cycleIndex][i];
		cycleList[cycleIndex][i]=cycleList[cycleIndex][j];
		cycleList[cycleIndex][j]=temp;
		total++;
		done=0;
		goodArr[i]=goodArr[j]=1;
	      }
	  }   
	}    
    }
}

int checkSame(int one,int two,int cycleLength)
{
  int i,j,k;
  int same;
  int tempArr[30];
  int dif;
  /*Hmmm if we add  (ONE[0]-TWO[0]) to all elements in one (do a shift) then check the resulting
  
  array and do the same for it's swap...
  */
  dif=cycleList[one][0]-cycleList[two][0];
  dif=(cycleLength+dif)%cycleLength; /*Get rid of negetive mods...*/
  for(i=0;i<cycleLength;i++)
    tempArr[i]=(cycleList[one][i]+dif)%cycleLength;
  same =1;
  for(i=0;i<cycleLength;i++)
    {
      if(tempArr[i]!=cycleList[two][i])
	{   same=0; break;}
    }
  if(same)
    return 1;
  /*swap*/
  for(i=0;i<cycleList;i++)
    tempArr[cycleList-1-i]=cycleList[one][i];
  dif=tempArr[0]-cycleList[two][0];
  dif=(dif+cycleLength)%cycleLength;
  for(i=0;i<cycleLength;i++)
    tempArr[i]=(tempArr[i]+dif)%cycleLength;
  same=1;
  for(i=0;i<cycleLength;i++)
    {
      if(tempArr[i]!=cycleList[two][i])
	{   same=0; break;}
    }
  if(same)
    return 1;
  else
    return 0;
}


int createCycleList(cycleLength)
{
  int i,j,k;
  int index,numberLeft;

  /*Do a DFS assignment of all n! possibilities*/
  numberleft=DFSWRITE(cycleLength,depth,index);
  /*Get old code here*/


  index=0;
  while(index < numberLeft)
    {
      for(i=index+1;i<numberLeft;i++)
	{
	  if(checkSame(index,i,cycleLength))
	    {
	      for(j=numberLeft-1;j>index+1;j++)
		{
		  for(k=0;k<cycleLength;k++)
		    {
		      cycleList[j-1][i]=cycleList[j][i];
		    }
		}
	      numberLeft--;
	    }
	}
    }
  return  numberLeft;
}


int createStandard(cycleLength)
{
  int i,j,k;
  int index;
  for(i=0;i<cycleLength;i++)
    stdList[0][i]=i;
  index=1;
  for(i=1;i<cycleLength;i++)
    {
      for(j=0;j<cycleLength;j++)
	stdList[index][j]=(stdList[index-1][j]+i)%cycleLength;
      index++;
    }
  for(i=0;i<cycleLength;i++)
    stdList[index][i]=(cycleLength-1)-i;
  for(i=1;i<cycleLength;i++)
    {
      for(j=0;j<cycleLength;j++)
	stdList[index][j]=(stdList[index-1][j]+i)%cycleLength;
      index++;
    }
  return 2*cycleLength;
}




int main()
{
  int i,j,k;
  int cycleLength;
  int stdNum;
  int cycleNum;
  
  cout <<"\nInput number of verticies:\n";
  cin >> cycleLength;
  
  if(cycleLength<3 || cycleLength>10)
    {
      cout <<"\nPlease input from 3-10 verticies\n";
      return 1;
    }
    
  stdNum=createStandard(cycleLength);
  
  cycleNum=createCycleList(cycleLength);


  return 0;
}