/* Constraint free BINARY CODING OF PERMUTATION

Maurice.Clerc@WriteMe.com
Last update 2005-03-27

What for?
---------
Any combinatorial optimisation problem can be coded as a binary one,
in order to be solved by a binary optimiser.
However, most of the time, this coding add some constraints, 
and the optimiser has to cope with them.
That is why a binary coding that does not add any constraint is useful.

Here is one that can be used each time the search space is a set of permutations P.

Let B be the set of binary strings that code for permutations.
With the present method whe have
a) size(B) > size(P)
b) an injection from P to B (coding)
c)  a surjection from B to P (decoding)

This last point is particularly interesting for optimisation: 
sometimes several bit strings code the same permutation, 
so you have then a higher probability to find it.

Coding scheme
-------------
Example 1: permutation 3 1 2
is the first number = 1? No => 0
is the first number = 2? No => 0
is the first number = 3? No => 1
is the second number = 1? Yes => 1
is the third number = 2? Yes* => 1
=> 00111

Example 2: permutation 3 2 1
is the first number = 1? No => 0
is the first number = 2? No => 0
is the first number = 3? Yes* => 1
is the second number = 1? No => 0
is the second number = 2? Yes => 1
is the third number = 1? Yes* => 1
=> 001011

* this answer is certain. So the code could be even more compact.

*/

/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/

#include <stdio.h>
#include <math.h>
#include <cstdlib>

#define N_max 30	// Max. length of the permutation
#define B_max 465	// N*(N+1)/2

// Structure(s)
struct int_list	{int size;int l[B_max];};

// Subprograms
int		alea_bit();
struct int_list coding(struct int_list permut);
struct int_list decoding(struct int_list bin,int N);

void main()
{
struct int_list bin;
int choice;
int	k,K;
int n,N;
struct int_list permut;
int s,S;

choice:
printf("\n 0 => END");
printf("\n 1 => coding one permutation");
printf("\n 2 => decoding one binary string");
printf("\n 3 => decoding random binary strings");
printf("\n Your choice?: ");
scanf("%i",&choice); if(choice<0 || choice>3) goto choice;

switch(choice)
{
case 0: goto end;
case 1: //------------------------ Coding (permutation => binary string)
printf("\n N? (0 for STOP): ");scanf("%i",&permut.size);
if(permut.size==0) break;

printf("\n Permutation? (%i different integers in [1, %i]): ",permut.size,permut.size);
for(n=0;n<permut.size;n++) scanf(" %i",&permut.l[n]);
bin=coding(permut);

printf("\nBit string length = %i \n",bin.size);
for(k=0;k<bin.size;k++) printf("%i",bin.l[k]);
printf("\n");


break;

case 2://------------------------- Decoding (binary string => permutation)
printf("\nBit string length? (0 for STOP): "); scanf("%i",&bin.size);
if(bin.size==0) break;

printf("Bit string?: ");
for (k=0;k<bin.size;k++) scanf("%i",&bin.l[k]);

permut_size_2:
N=(int)(0.5+sqrt(0.25+2*bin.size));
printf("\nPermutation length? (>= %i): ",N);scanf("%i",&permut.size);
if(permut.size<N) goto permut_size_2;

permut=decoding(bin,permut.size);

	printf("\n");
	for(k=0;k<bin.size;k++) printf("%i",bin.l[k]);
	printf(" => ");
	for(n=0;n<permut.size;n++) printf("%i ",permut.l[n]);

break;

case 3: // Decoding random binary strings
printf("\nBit string length? (0 for STOP): "); scanf("%i",&bin.size);
if(bin.size==0) break;

printf("\nNumber of strings to generate?: "); scanf ("%i",&S);
if(S==0) break;

permut_size_3:
N=(int)(1+sqrt(0.25+2*bin.size));
printf("\nPermutation length? (>= %i): ",N);scanf("%i",&permut.size);
if(permut.size<N) goto permut_size_3;

for (s=0;s<S;s++)
{
	// Generate the string
	for (k=0;k<bin.size;k++) bin.l[k]=alea_bit();
	// Decode
	permut=decoding(bin,permut.size);
	// Print
	printf("\n");
	for(k=0;k<bin.size;k++) printf("%i",bin.l[k]);
	printf(" => ");
	for(n=0;n<permut.size;n++) printf("%i ",permut.l[n]);
}

break;
}

goto choice;

end:;
}

//=============================================== ALEA
int alea_bit()
{
	if(rand()<RAND_MAX/2) return 0;
	return 1;
}

//=============================================== CODING
struct int_list coding(struct int_list permut)
{
	struct int_list bin;
	int first,i,j,n,num,r;
	int	used[N_max];
	
	i=-1;	// rank of the number to code
j=0;	// rank of the bit to set
for (n=0;n<permut.size;n++) used[n]=0; // Numbers (n+1) not yet used

coding:
i=i+1;	num=permut.l[i];
r=0;
first:
// Look for the first non used, starting from r

for(first=r;first<permut.size;first++) if(used[first]==0) goto bin;
goto result;

bin:
// code
if(first+1==num) 
{
	bin.l[j]=1;j=j+1;
	used[first]=1;
	goto coding;
}
else
{
	bin.l[j]=0;j=j+1;
	r=r+1;
	goto first;
}

result:
bin.size=j;
return bin;
}

//=============================================== DECODING
struct int_list decoding(struct int_list bin,int N0)
{
struct int_list permut;
int	i,j,j0,k,n,N,r;
int	used[N_max];

for (n=0;n<N0;n++) used[n]=0; // Numbers (n+1) not yet decoded

j=0; // Rank of the current bit
i=0; // Rank of the number to decode

decoding:

// Find the first 1, starting from j
j0=j;
for(k=j0;k<bin.size;k++) if(bin.l[k]==1) {j=k+1;goto number;}
goto result;

number:
k=k-j0;// k = number of consecutive 0, starting from j
// Count k non already found numbers

r=-1;
for(n=0;n<N0;n++) 
{
	if(used[n]>0) continue;
	r=r+1;
	if(r==k)
	{
		used[n]=1;
		permut.l[i]=n+1;
		i=i+1;
		goto decoding;
	}
}

result:

// Possibly complete the permutation
//	Note: deterministic method
//	For stochastic optimisers, it could be better to use a random one
if(i<N0) 
{	
	for (n=0;n<N0;n++)
	{ 
		if(used[n]>0) continue;
		permut.l[i]=n+1;
		i=i+1; if(i>=N0) goto end;
	}
}
end:
permut.size=i;
return permut;
}