/* 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
#include
#include
#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 permutation)
printf("\nBit string length? (0 for STOP): "); scanf("%i",&bin.size);
if(bin.size==0) break;
printf("Bit string?: ");
for (k=0;k= %i): ",N);scanf("%i",&permut.size);
if(permut.size ");
for(n=0;n= %i): ",N);scanf("%i",&permut.size);
if(permut.size ");
for(n=0;n0) 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(i0) continue;
permut.l[i]=n+1;
i=i+1; if(i>=N0) goto end;
}
}
end:
permut.size=i;
return permut;
}