//---------------------------------------------------------------
// GENERATING (SIGNED, COLOURED) PERMUTATIONS BY MIN or MAX FLIPS 
// Research with: Aaron Williams, Joe Sawada, Ben Cameron
// Programmed by: Joe Sawada 2013-2021
//---------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>

#define MAX_N 20
#define Max(a,b) (a > b) ? a : b

int MAX=0, MIN=0, NORMAL=0, SIGNED=0,COLOURED=0; 
int GEN=0, RANK=0, UNRANK=0, SUCCESSOR=0;
int n, k, type, a[MAX_N], sign[MAX_N], f[MAX_N], c[MAX_N];
long int rank, total, powK[MAX_N], factorial[MAX_N];

//-------------------------------------------------------------
void Input() {
int i,j;

	printf(" ----------------------\n");               
	printf(" Permutation Generation \n"); 
	printf(" ----------------------\n");               
	printf("  1. Max Flip \n");
	printf("  2. Min Flip\n");
	printf("  3. Max Flip (Signed) \n");
	printf("  4. Min Flip (Signed) \n");
	printf("  5. Min Flip (Coloured) \n");
	printf("\n");
	printf(" ----------------------\n");               
	printf(" Permutation Ranking \n"); 
	printf(" ----------------------\n");               
	printf("  6. Max Flip \n");
	printf("  7. Min Flip\n");
	printf("  8. Max Flip (Signed) \n");
	printf("  9. Min Flip (Signed) \n");
	printf(" 10. Min Flip (Coloured) \n");
	printf("\n");
	printf(" ----------------------\n");               
	printf(" Permutation UnRanking \n"); 
	printf(" ----------------------\n");               
	printf(" 11. Max Flip \n");
	printf(" 12. Min Flip\n");
	printf(" 13. Max Flip (Signed) \n");
	printf(" 14. Min Flip (Signed) \n");
	printf(" 15. Min Flip (Colored) \n");
	printf("\n");
	printf(" ----------------------\n");               
	printf(" Permutation Successor\n"); 
	printf(" ----------------------\n");               
	printf(" 16. Max Flip \n");
	printf(" 17. Min Flip\n");
	printf(" 18. Max Flip (Signed) \n");
	printf(" 19. Min Flip (Signed) \n");
	printf(" 20. Min Flip (Colored) \n");

	printf("\n ENTER selection #: ");    scanf("%d", &type);
	
	if (type < 0 || type > 20)  {
		printf("\n INVALID ENTRY\n\n");
		exit(0);
	}	

	// long int constraints: MAX n seems to be 20 or 16 (Signed)
	printf(" ENTER length n: ");			
	scanf("%d", &n);
	
	factorial[0] = 1;
	for (j=1; j< MAX_N; j++) factorial[j] = factorial[j-1] * j;
	
	if (type % 5 == 1 || type % 5 == 2) NORMAL = 1;
	if (type % 5 == 4 || type % 5 == 3) SIGNED = 1;
	if (type % 5 == 0) COLOURED = 1;
	
	if (type % 5 == 1 || type % 5 == 3) MAX = 1;
	if (type % 5 == 4 || type % 5 == 2 || type % 5 == 0) MIN = 1;

	if (COLOURED) {
		printf(" ENTER colors k: ");			
		scanf("%d", &k);
	}
	else if (SIGNED) k = 2;
	else k = 1;
	
	powK[0] = 1;
	for (j=1; j< MAX_N; j++) powK[j] = powK[j-1] * k;
	
	if (type >= 1 && type <= 5)  GEN = 1;
	else if ((type >=6  && type <= 10) || (type >=16  && type <= 20)) {
		if (type >=6  && type <= 10) RANK = 1;
		if (type >=16  && type <= 20) SUCCESSOR = 1;

		if (type != 10 && type != 20) {
			printf(" ENTER permutation (separated by spaces): ");
			for (i=1; i<=n; i++) scanf("%d", &a[i]);
			for (i=1; i<=n; i++) {
				if (a[i] < 0) {
					a[i] = -a[i];
					sign[i] = 1;
				}
				else sign[i] = 0;
			}
		}
		else {
			printf(" ENTER coloured permutation of form: p_1,c_1  p_2,c_2  ...  ");
			for (i=1; i<=n; i++) scanf("%d,%d", &a[i], &sign[i]);
		}
	}
	else if (type >=11  && type <= 15) {
		UNRANK = 1;
		if (NORMAL == 1) rank = factorial[n];
		else rank = factorial[n] * powK[n];
		printf(" ENTER rank (between 1 and %ld): ", rank);
		scanf("%ld", &rank);
	}	   
	printf("\n");	
}
//----------------------------------------
void Init() {
	int j;
	
	//==============
	// INITIAL PERM	
	//==============
	for (j=1; j<=n; j++) a[j] = j;
	for (j=1; j<=n; j++) sign[j] = 0;
	
	//===========
	// INIT NEXT
	//===========
	for (j=0; j<=n+1; j++) c[j] = 0;
	for (j=0; j<=n+1; j++) f[j] = j;
}

//-------------------------------------------------
// OPERATIONS ON PERMUTATIONS
//-------------------------------------------------
void RotateRight(int t, int j) {
int i, b[MAX_N];

	for (i=1; i<=t-j; i++) b[i+j] = a[i];
	for (i=1; i<=j; i++) b[i] = a[t-j+i];
	for (i=1; i<=t; i++) a[i] = b[i];

	for (i=1; i<=t-j; i++) b[i+j] = sign[i];
	for (i=1; i<=j; i++) b[i] = sign[t-j+i];
	for (i=1; i<=t; i++) sign[i] = b[i];
}
//-------------------------------------------------
void RotateLeft(int t, int j) {
int i, b[MAX_N];

	for (i=j+1; i<=t; i++) b[i-j] = a[i];
	for (i=1; i<=j; i++) b[t-j+i] = a[i];
	for (i=1; i<=t; i++) a[i] = b[i];

	for (i=j+1; i<=t; i++) b[i-j] = sign[i];
	for (i=1; i<=j; i++) b[t-j+i] = sign[i];
	for (i=1; i<=t; i++) sign[i] = b[i];
}
//-------------------------------------------------
void Flip(int t) {
int i, b[MAX_N];

	for (i=1; i<=t; i++) b[i] = a[t-i+1];
	for (i=1; i<=t; i++) a[i] = b[i];

	//============================
	// Flip Signs for colored case
	//============================
	if (k > 1) {
		for (i=1; i<=t; i++) b[i] = sign[t-i+1];
		for (i=1; i<=t; i++) sign[i] = (b[i]+1) % k;
	}
}
//-------------------------------------------------
void FlipSign(int t) {
int i;

	for (i=1; i<=t; i++) sign[i] = (sign[i]+1)%2;
}
//----------------------------------------
// UNRANKING
//----------------------------------------
void UnRankMin(long int rank, int t){
int j,x;

	if (t == 1) { a[1] = 1; return; }

	x =  (rank-1) / factorial[t-1];
	rank = rank - x * factorial[t-1];

	UnRankMin(rank, t-1);
	
	a[t] = t - x;
	for (j=1; j<t; j++)   a[j]  = 1 + (a[j] + a[t] - 1) % t;
}

//----------------------------------------
void UnRankMinColoured(long int rank, int t){
	int j,x;

	if (t == 1) { 
		a[1] = 1; 
		sign[1] = rank - 1;
		return; 
	}
	
	x = (rank-1) / (factorial[t-1] * powK[t-1]);
	rank = rank - x * factorial[t-1] * powK[t-1];
		
	// x ranges from 0 to kn-1
	a[t] = t - (x % t);
	sign[t] = (int) x/t;
		
	UnRankMinColoured(rank, t-1);
	
	for (j=1; j<t; j++)  {
		a[j] =  1 + (a[j] + a[t] - 1) % t;		
		if (a[j] <  a[t]) sign[j] = (sign[j] + sign[t]) % k;
		if (a[j] >  a[t]) sign[j] = (sign[j] + sign[t] + 1) % k;
	}
}
//----------------------------------------
void UnRankMax(long int rank, int t) {
int d;

	//===========
	// BASE CASE	
	//===========
	if (t == 2) {
		if(rank == 1) { a[1] = 1; a[2] = 2;}
		if(rank == 2) { a[1] = 2; a[2] = 1;}
		return;
	}

	a[t] = t;
	if (rank % 2 == 0) {
		UnRankMax( 2*((rank-1)/(2*t)) + 2, t-1);
		d =  2*t - (rank % (2*t));
	}
	else {
		UnRankMax( 2*((rank-1)/(2*t)) + 1, t-1);
		d =  (rank-1) % (2*t);
	}
	RotateLeft(t,d/2);
}
//----------------------------------------
void UnRankMaxSigned(long int rank, int t) {
int d;

	a[t] = t;  sign[t] = 0;
	//===========
	// BASE CASE	
	//===========
	if (t == 1) {
		if (rank == 2) sign[1] = 1;
		return;
	}

	d = (rank-1) % (4*t);
	if (d >= 2*t) {
		d = 4*t - d - 1;
		UnRankMaxSigned( 2*((rank-1)/(4*t)) + 2, t-1);
	}
	else UnRankMaxSigned( 2*((rank-1)/(4*t)) + 1, t-1);
	
	if (d % 2 == 0) {
		FlipSign(d/2);
		RotateLeft(t,d/2);
	}
	else {
		Flip(t);
		RotateRight(t,d/2);
		FlipSign(d/2);
	} 
}
//----------------------------------------
// RANKING
//----------------------------------------
long int RankMin(int t){
int j;

	if (t == 1) return 1;
	for (j=1; j<t; j++)  a[j] = (a[j] - a[t] + t) % t;
	return ((t-a[t]) * factorial[t-1] + RankMin(t-1));
}
//----------------------------------------
long int RankMinColoured(int t){
	int j;
		
	if (t == 1) return sign[1] + 1;
	
	for (j=1; j<t; j++)  {
		if (a[j] <  a[t]) sign[j] = (sign[j] - sign[t] + k) % k;
		if (a[j] >  a[t]) sign[j] = (sign[j] - sign[t] - 1 + k) % k;
		a[j] = (a[j] - a[t] + t) % t;
	}

	return (( (sign[t]+1) * t - a[t]) * factorial[t-1] * powK[t-1] + RankMinColoured(t-1));
}
//----------------------------------------
long int RankMax(int t) {
long int i,d,x,p;

	//===========
	// BASE CASES	
	//===========
	if (t == 2 && a[1] ==1) return 1;
	if (t == 2 && a[1] ==2) return 2;
	
	//=====================================
	// Determine position of largest value 
	//=====================================
	for (i=1; i<=t; i++) if (a[i] == t) p = i;

	//======================================================================
	// Rotate to either the first or last permutation in the bracelet class
	//======================================================================
	d = 2*(t-p);
	RotateRight(t,t-p);
	
	//==================================================================================
	// The parity indicates whether or not the rotate perm is first or last in the class 
	//==================================================================================
	x = RankMax(t-1); 
	if (x % 2 == 0) return (t*x - d);
	else return (t*(x-1) + d+1);
}
//----------------------------------------
long int RankMaxSigned(int t) {
long int i,d,x,p;

	//===========
	// BASE CASE	
	//===========
	if (t == 1 && sign[1] == 0) return 1;
	if (t == 1 && sign[1] == 1) return 2;
	
	//=====================================
	// Determine position of largest value 
	//=====================================
	for (i=1; i<=t; i++) if (a[i] == t) p = i;

	//===========================================================================
	// Rotate/Flip to either the first or last permutation in the bracelet class
	//===========================================================================
	d = 2*(t-p);
	RotateRight(t,t-p);
	FlipSign(t-p);	
	
	if (sign[t] == 1) {
		FlipSign(t);
		d += 2*t;
	}
		
	//==================================================================================
	// The parity indicates whether or not the rotate perm is first or last in the class 
	//==================================================================================
	x = RankMaxSigned(t-1); 
	if (x % 2 == 0) return (2*t*x - d);
	else return (2*t*(x-1) + d+1);
}
//----------------------------------------
// SUCCESSORS
//----------------------------------------
void SuccessorMin() {
int j, incr=0;
	
	for (j=1; j<n; j++) {
		if (a[j] < a[j+1]) incr++;
		if (incr == 2 || (incr == 1 && a[j+1] < a[1])) break;
	}
	Flip(j);
}
//----------------------------------------
void SuccessorMinColoured() {
int j, incr=0;
	
	for (j=1; j<n; j++) {
		if (a[j] < a[j+1]) incr++;
		if (incr == 2 || (incr == 1 && a[j+1] < a[1])) break;
		
		if (k > 1 && a[j] < a[j+1] && (sign[j+1] - sign[j] + k) % k != 1) break;
		if (k > 1 && a[j] > a[j+1] &&  sign[j+1] != sign[j]) break;
	}
	Flip(j);
}
//----------------------------------------
void SuccessorMax() {
	int j, p1, p2, p3, d=0;
	
	for (j=1; j<=n; j++) {
		if (a[j]  == 1) p1 = j; 
		if (a[j]  == 2) p2 = j; 
		if (a[j]  == 3) p3 = j; 
		if (a[j] != j) d = j;
	}
	if ((p1 < p2 && p2 < p3) || (p2 < p3 && p3 < p1) || (p3 < p1 && p1 < p2)) Flip(n);
	else Flip( Max(d-1,2) );
}
//----------------------------------------
void SuccessorMaxSigned() {
int j, p1, p2, s1, s2, d=1;
	
	for (j=1; j<=n; j++) {
		if (a[j]  == 1) { p1 = j; s1 = sign[j]; }
		if (a[j]  == 2) { p2 = j; s2 = sign[j]; }
		if (a[j] != j) d = j+1;
	}
	if ((p1 < p2 && s1 == s2) || (p2 < p1 && s1 != s2)) Flip(n);
	else Flip( Max(d-2,1) );
}
//----------------------------------------
// FLIP SEQUENCE GENERATION 
//----------------------------------------
int NextMin() {
int j;

	j = f[2];
	f[2] = 2;
	c[j]++;
	if (c[j] == j-1 || j == 2) {
		c[j] = 0;
		f[j] = f[j+1];
		f[j+1] = j+1;
	}
	if (j == n+1) return(0);
	return(j);
}
//----------------------------------------
int NextMinColoured() {
int j;

    if (k == 1) { j = f[2];   f[2] = 2;  }
    else        { j = f[1];   f[1] = 1;  }
    
	c[j]++;
	if (c[j] == k*j-1) {
		c[j] = 0;
		f[j] = f[j+1];
		f[j+1] = j+1;
	}
	if (j == n+1) return(0);
	return(j);
}
//----------------------------------------
int NextMax() {
int j;

	j = f[n];
	f[n] = n;
	c[j]++;
	if (c[j] == j || j == n) {
		c[j] = 0;
		f[j] = f[j-1];
		f[j-1] = j-1;
	}
	if (j == 1) return(0);
	return(j);
}
//----------------------------------------
int NextMaxSigned() {
int j;

	j = f[n];
	f[n] = n;
	c[j]++;
	if (c[j] == 2*j+1 || j == n) {
		c[j] = 0;
		f[j] = f[j-1];
		f[j-1] = j-1;
	}
	if (j == 0) return(0);
	return(j);
}
//----------------------------------------
void Print() {
	int i;
	
	for (i=1; i<=n; i++) {
		if (COLOURED) printf("(%d,%d) ", a[i], sign[i]);
		else {
			if (sign[i] == 0 || !SIGNED)  printf(" %d ", a[i]);
			else printf("-%d ", a[i]);
		}
	} 
	if (!RANK) printf("\n");  
	total++;
}
//----------------------------------------
void Gen() {
int j;

	do {
		Print(); 

		if (MIN && NORMAL)   j= NextMin();
		if (MAX && NORMAL)   j= NextMax();
		if (MIN && SIGNED)   j= NextMinColoured();
		if (MAX && SIGNED)   j= NextMaxSigned();
		if (MIN && COLOURED) j= NextMinColoured();

		Flip(j);

	} while (j>0);
	
	printf("Total = %ld\n\n", total);
}
//----------------------------------------
int main() {
		
	Input();
	
	if (GEN) {
		Init();
		Gen();
	}
	if (RANK) {
		printf("The rank of permutation ");
		Print();
				
		if (MIN && NORMAL) rank = RankMin(n);
		if (MIN && SIGNED) rank = RankMinColoured(n);
		if (MAX && NORMAL) rank = RankMax(n);
		if (MAX && SIGNED) rank = RankMaxSigned(n);
		if (MIN && COLOURED) rank = RankMinColoured(n);
		printf(" is:  %ld\n\n", rank);
	}
	if (UNRANK) {
		if (MIN && NORMAL) UnRankMin(rank,n);
		if (MIN && SIGNED) UnRankMinColoured(rank,n);
		if (MAX && NORMAL) UnRankMax(rank,n);
		if (MAX && SIGNED) UnRankMaxSigned(rank,n);
		if (MIN && COLOURED) UnRankMinColoured(rank,n);
		printf("The permutation of rank %ld is: ", rank);
		Print();
	}
	if (SUCCESSOR) {
		printf("The successor of permutation ");
		Print();
				
		if (MIN && NORMAL) SuccessorMinColoured();
		if (MIN && SIGNED) SuccessorMinColoured();
		if (MAX && NORMAL) SuccessorMax();
		if (MAX && SIGNED) SuccessorMaxSigned();
		if (MIN && COLOURED) SuccessorMinColoured();
		printf(" is:  ");
		Print();
	}
}