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

	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 100 //Maximum number of elements. 

#define sliceNbMax 20 // In order to cope with big integers, one can "divide" them
											// into "sliceNbMax" slices
#define sliceSize 5 // Each slice can be used to code at most sliceSize elements
										// of the factorial numbering
										// Each slice of rank k (in (0,...,sliceNbMax-1)
										// is for numbers in (1, ... (sliceSize+1)!)*((sliceSize+1)!)
#include <stdio.h>
#include "math.h"

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

// Subprograms
struct code permut2code(struct permutation permut);
struct permutation code2permut(struct code codePerm, int N);
int factor(int a, int b); // b!/a!


//==========================================
int main()
{
	struct code codePerm;
	int option;
	struct permutation permut=	{13,   {4,3,6,5,1,2,10,9,7,8,12,13,11}};
	int r;
	int s;

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

	// Data
	switch(option)
	{
		case 0:
			// See the above initialisation of permut

		break;

		case 1:
			permut.N=13;
			codePerm.size=3;
			codePerm.code[0]=38;  
			codePerm.code[1]=16131;
			codePerm.code[2]=243;

		break;
	}

	// Algorithm
	switch(option)
	{
		case 0:// Here I know the permutation, and I want its code
			printf("\nPermutation of %i elements \n(",permut.N);
			for(r=0;r<permut.N;r++) printf(" %i",permut.rank[r]);
			printf(")");
			printf("\nsliceSize %i",sliceSize);
			printf("\n=>");

			codePerm=permut2code(permut);

			printf("\nCode: ");
			for(s=0;s<codePerm.size;s++)
				printf("%i ",codePerm.code[s]);
		
		break;
		
		case 1: // Here I know the code, and I want the permutation
		printf("\n %i elements",permut.N);
		printf("\nCode: ");
		for(r=0;r<codePerm.size;r++) printf("%i ",codePerm.code[r]);
		printf("\nNumber of slices: %i",codePerm.size);
		printf("\nsliceSize %i",sliceSize);
		printf("\n=>");

		permut=code2permut(codePerm,permut.N);

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

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

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

	for(r=0;r<N-1;r++)
	{
		alpha[r]=sequence[r]-1;
		// 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]);

	// Coding
	codePerm.size=(N-1)/sliceSize; 
	if((N-1)%sliceSize>0) codePerm.size=codePerm.size+1; // Number of slices
	printf("\nNumber of slices: %i",codePerm.size);
	
	k2=1;
	for(s=0;s<codePerm.size;s++) codePerm.code[s]=0;

		s=codePerm.size-1;

		for(r=0;r<N-1;r++) // Loop on alpha
		{
				k=r%sliceSize;

				codePerm.code[s]=codePerm.code[s]+alpha[N-2-r]*factor(k2,r+1);
				printf("\n s= %i  r= %i  N-2-r= %i, alpha %i,  factor(%i,%i)",
							s,r,N-2-r,alpha[N-2-r],  k2,r+1);

			if(k==sliceSize-1)
			{
				s=s-1;
				k2=(codePerm.size-s-1 )*sliceSize+1;
				printf("\n");
			}
		}

		return codePerm;
}
//================================================= DECODING
struct permutation code2permut(struct code codePerm, int N)
{
	int codeR;
	int k1,k2,k3;
	int numFact[NMax-1]={0};

	struct permutation permut;
	int r,rBegin,rEnd, r2,r3,r4;
	int rank;
	int s;
	int sequence[NMax];
	
	permut.N=N;

	s=0;
	rank=0;
	r=2;
	r2=N-1-(codePerm.size-1)*sliceSize;

sliceDecode:
	codeR=codePerm.code[s];
	printf("\n slice %i, code %i",s,codeR);

	k1=(codePerm.size-s-1)*sliceSize+1;

	if(s>0) 
	{
		rBegin=r2 + (s-1)*sliceSize;
		rEnd=rBegin+sliceSize-1;
		k2=k1+sliceSize-1;
	}
	else 	
	{	
		rBegin=0;rEnd=r2-1;
		k2=N-1;
	}

convert:
	k3=factor(k1,k2);
	numFact[rank]=codeR/k3;
	codeR=codeR%k3;
	printf("\n rank %i, numFact %i, factor(%i,%i)",rank,numFact[rank], k1,k2);

	k2=k2-1;

	if(k2>=k1)
	{
		r=r+1;
		rank=rank+1;
		goto convert;
	}
	
	rank=rank+1;
	numFact[rank]=codeR;

	if(s<codePerm.size-1)
	{
		s=s+1;
		printf("\n");
		goto sliceDecode;
	}

	printf("\nFactorial numbering: ");
	for(r=0;r<N-1;r++) printf("%i ",numFact[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=numFact[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];

return permut;

}
//===================================== FACTOR
int factor(int a, int b)
{ // b!/a!
	int f=a+1;
	int i;

	if(b<=a) return 1;
	if(b==a+1) return f;
	
	for(i=a+2;i<=b;i++) f=f*i;
	return f;
}