//
// This is NOT a GA for TSP. This is an example of a binary encoding for
// the TSP inspired by a talk by Chaitin and a paper by WPC.
// A tour is represented as a binary string representing a sequence
// of swaps by a bubbleSort process, i.e. the string is a sequence of
// instructions for constructing a tour. For a tour of n cities the
// sequence is of length n(n-1)/2, i.e. maximum number of steps in
// a bubble sort (maximum trajectory). If S[i] = 1 then a swap takes place
// in the kth step of the bubbleSort (see evaluate method below).
//
// The encoding permits 2^(n(n-1)/2) chromosomes for n! tours. A more
// compact encoding will exist for a mergeSort representation, taking
// n.log(n) bits
//

public class GATSP {
    int n,m;
    private int[] P; // permutation, a tour
    private int[] S; // sequence of actions
    private boolean overflow;

    public GATSP(int n){
	this.n   = n;
	m        = n*(n-1)/2;
	P        = new int[n];
	S        = new int[m];
	overflow = false;
	for (int i=0;i<n;i++) P[i] = i;
	for (int i=0;i<m;i++) S[i] = 0;
    }

    public void show(){
	for (int i=0;i<m;i++) System.out.print(S[i]);
	System.out.print(" -> ");
	for (int i=0;i<n;i++) System.out.print(P[i]);
	System.out.println();
    }
    //
    // show binary string S and the corresponding permutation P
    //

    public void getNext(){
	boolean done = false;
	for (int i=0;i<m && !done;i++){
	    S[i]     = 1 - S[i];
	    done     = S[i] == 1;
	    overflow = i == m-1 && S[i] == 0;
	}
    }
    //
    // get the next binary string S in lex order
    //

    public boolean hasNext(){return !overflow;}

    private void swap(int i, int j){
	int temp = P[i]; P[i] = P[j]; P[j] = temp;
    }

    public void evaluate(){
	int k = 0;
	for (int i=0;i<n;i++) P[i] = i;
	for (int i=n-1;i>0;i--)
	    for (int j=0;j<i;j++){
		if (S[k] == 1) swap(j,j+1);
		k++;
	    }
    } 
    //
    // evaluate S by a bubbleSort process that goes from order to disorder
    // 

    public static void main(String[] args){
	if (args.length == 0){
	    System.out.println("GATSP n");
	    System.out.println("deliver all 2^(n(n-1)/2) chromosomes with resultant n-permutations");
	    return;
	}	
	GATSP gatsp = new GATSP(Integer.parseInt(args[0]));
	while (gatsp.hasNext()){
	    gatsp.evaluate();
	    gatsp.show();
	    gatsp.getNext();
	}
    }    
}