/* ArrangeToCycle.c */
/* input: integer N and any arrangement of numbrs 1,2,...,N
  output: cyclic equivalent of that arrangement
  -1,-2 in array C mean to print parentheses {, } respectively
*/

#define NN 100

#include <stdio.h>

void main(void)
{
 int A[NN],B[NN],C[NN],FX[NN], N,H,I,J,K,HB,HC,L,SUM=0,ERR; 
   /* H-->FX, C[I], B[J], L = length of cycle without repetition */
INX:
 for (K=0; K<NN; K++) A[K]=B[K]=C[K]=FX[K]=0;

 puts("input zero anywhere to terminate program");
 printf("Input number N (0<N<%d) of objects (natural numbers):  ",NN);
   scanf("%d",&N); getchar();
   if (!N) goto FIN;
   if (N<1) {puts("Error: number is negative"); goto INX;}
   if (N>=NN) {puts("Error: number is too large"); goto INX;}

ERR=0;
 printf("Input %d distinct natural numbers between 1 and %d inclusive\n",N,N);
  puts("separated by commas or spaces input zero to start new input");
 for (J=1; J<=N; J++)
  {scanf("%d",&A[J]); getchar(); if (!A[J]) goto FIN;}

 for (J=1; J<=N; J++)
  {
   if (!A[J]) {puts("zero input means terminate program\n"); goto FIN;}
   if (A[J]<1)
    {printf("ERROR: Negative number %d\n",A[J]); ERR++;}
   if (A[J]>N)
    {printf("ERROR: number %d larger than %d\n",A[J],N); ERR++;}
  }

 for (J=1; J<=N; J++)
  for (K=1; K<J; K++)
    if (A[K]==A[J])
     {printf("ERROR: duplicate numbers %d and %d\n",A[K],A[J]); ERR++;}

 if (ERR)
  {
   printf("Total number of errors = %d\n",ERR);
   puts("input all numbers again\n");
   goto INX;
  }

 puts("Permutation in the form of an arrangement is");
 for (J=1; J<N; J++) printf("%d,",A[J]); printf("%d",A[N]); puts("");


 for (J=1; J<=N; J++) B[J]=A[J];



 puts("processing arangement and converting it into cyclic form");

 H=I=0;           /* B[1] not zero */
LP:
 J=0; while (!B[J]) J++;    /* Find index of first non-zero object in array B */
 if(J>N) goto PRNTC;       /* if array B all zeros, then print C, end program */
 if (J == B[J])
  {FX[0]++; H++; FX[H]=J; B[J]=0; goto LP;}  /* Copy fixed point to FX[] */
 HB = J; C[I]=-1; I++; HC = I; C[HC]=HB; /* Copy index of first object in B to C; start cycle */
 L=1;
 /* for (K=0; K<16; K++) printf("C[%d]=%d  ",K,C[K]); puts(""); getchar(); */

 J=B[J];
 while (J != HB) {++I; C[I]=J; L++;  K=J; J=B[J]; B[K]=0;} /* Copy cycle */
 B[J]=0; I++; C[I]=-2; I++;    /* end of cycle at J and I */
                 SUM = SUM + L - 1;

 /* for (K=0; K<16; K++) printf("*C[%d]=%d  ",K,C[K]); puts(""); getchar(); */

 goto LP;

PRNTC:

 /* for (K=0; K<16; K++) printf("**C[%d]=%d  ",K,C[K]); puts(""); getchar(); */

 I=0;
 while (C[I])
  {
   if (C[I]==-1) printf("("); else
    if (C[I]==-2) printf(")"); else
    if (C[I+1] == -2)printf("%d",C[I]); else printf("%d ",C[I]);
   I++;
  }
  
 if (!H) {puts("            (No fixed points)"); goto OE;}
 K=H;
 printf("   fixed points: ");
  for (H=1; H<=K; H++) printf("(%d)",FX[H]); puts("");

OE:
 if (SUM & 1) puts("permutation is odd"); else puts("permutation is even");

FIN:
 puts("\npress Enter key to terminate program");
 getchar();

}