/*
 * Permutation Coding/Decoding by using Factorial Numeration
 * Copyright (C) Maurice 2008 <Maurice.Clerc@WriteMe.com>
 * Version 2008-08-16

	Any permutation of N elements can be numbered by an integer code in 
	{1,2, ... N!} and vice-versa.
	In this program, I apply methods inspired by the ones of C.-A. Laisant (1888),
	and of Marin Mersenne (1630?).

 * 
 * Permutation Coding/Decoding is free software: you can redistribute it and/or
 * modify it under the terms of the GNU General Public License version 3
 * as published by the Free Software Foundation
 * See http://www.gnu.org/licenses/
 * 
 */

#define NMax 13 //Maximum number of elements. 
								// WARNING: using a higher value is not valid with 
								// the classical "long int"
#include <stdio.h>

// Structures
struct permutation {int N; int rank[NMax];};

// Subprograms
long int permut2code(struct permutation permut);
struct permutation code2permut(long int code, int N);

// Global variables
long int fact[NMax];

//==========================================
int main()
{
	long int code;
	int option;
	struct permutation permut=	{6,  {4,3,6,5,1,2}};
	//struct permutation permut=	{13,  {4,3,6,5,1,2,10,9,7,8,12,13,11}}; // Data for coding: {N, ranks}
	int r;

	option=1; // 0 => coding, 1 => decoding

	// Data
	switch(option)
	{
		case 0:
			// See the above initialisation of permut
			// Prepare factorials
			fact[0]=1; for(r=1;r<permut.N;r++) fact[r]=fact[r-1]*(r+1);
		break;

		case 1:
			permut.N=6;//13 ; 
			code=430;//1528452964; 
		break;
	}

	// Algorithm
	switch(option)
	{
		case 0:// Here I know the permutation, and I want its code
			code=permut2code(permut);

			printf("\nPermutation (");
			for(r=0;r<permut.N;r++) printf(" %i",permut.rank[r]);
			printf(")");
			printf("\nCode %i",code);
		
		break;
		
		case 1: // Here I know the code, and I want the permutation
		permut=code2permut(code,permut.N);
		
		printf("\nCode: %i",code);
		printf("\nPermutation (");
		for(r=0;r<permut.N;r++) printf("%i ",permut.rank[r]);
		printf(")");
		break;
	}

	return (0);
}
//================================================= CODING
long int permut2code(struct permutation permut)
{
	int alpha[NMax-1]={0};
	long int code;
	int N=permut.N;
	int r,r2;
	int rEnd;
	int sequence[NMax];

	for(r=0;r<N;r++) sequence[r]=permut.rank[r];

	rEnd=-1;
	for(r=0;r<N-1;r++)
	{
		alpha[r]=sequence[r]-1;
		if(alpha[r]>0) rEnd=r; // rank of the last non null alpha
		// Decrease	
		for(r2=r+1;r2<N;r2++) if (sequence[r2]>sequence[r]) sequence[r2]=sequence[r2]-1;
	}
	
	printf("\nFactorial numbering:");
	for(r=0;r<N-1;r++) printf(" %i",alpha[r]);
	code=0;	
	if(rEnd>=0)
	{
		for(r=0;r<=rEnd;r++)
			code=code+alpha[r]*(fact[N-r-2]);
	}

	return code;
}
//================================================= DECODING
struct permutation code2permut(long int code, int N)
{
	long int codeR,codeR1;
	long int numFact[NMax-1]={0};
	long int numFactInv[NMax-1]={0};
	struct permutation permut,permutInv;
	int r,rEnd, r2,r3,r4;
	int sequence[NMax];

	permut.N=N;
	codeR=code;
	r=2;
convert: // Convert into "factorial numbering"
	numFact[r-2]=codeR%r; // remaining
	codeR1=codeR;
	codeR=codeR/r; // Quotient

	if(codeR>0) 
	{
		r=r+1;
		goto convert;
	}
	rEnd=r-1;
	numFact[rEnd-1]=codeR1;


	printf("\nFactorial numbering: ");
	for(r=0;r<N-1;r++) numFactInv[N-2-r]=numFact[r];
	for(r=0;r<N-1;r++) printf("%i ",numFactInv[r]);

	//Generate permutation
	for(r=0;r<N;r++) sequence[r]=r+1; // "Null" permutation to begin

	for(r=0;r<N-1;r++)
	{
		r3=numFactInv[r];
		permut.rank[r]=sequence[r3];
		if(r3<N-1) // Compact sequence[]
		{
			for(r4=r3;r4<N-1;r4++) sequence[r4]=sequence[r4+1];
		}
	}	

	// Complete
	permut.rank[N-1]=sequence[0];

printf("\n");for(r=0;r<N;r++) printf("%i ",permut.rank[r]);

return permut;

}