# A Inver-over approach.

 

use strict;
use List::Util qw/shuffle/;
my $pop_size   = 50;
my $number_column = 20;
my @population;
my $p = 0.02;#mutation rate.
my @target = (0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19); 

 
#procedure inver-over
#random initialization of the population P.

for (0..$pop_size-1){
 $population[$_] = genotype();
}
 
for my $generation (0..1000) { #not satisfied termination condition of generations
 print"generation: $generation\n";
 
 foreach my $gene (@population){
  my @temp_gene = split /,/, $gene;
  my $pos_c = int(rand($number_column));
  my $c =  $temp_gene[$pos_c];
  my $pos_c_prime=9999;
  my $c_prime = 9999;
  #print "temp gene: @temp_gene\n";
  #print "pos c: $pos_c\n";
  #print "c: $c\n";
  
  while(){# REPEAT
  
  if(rand()<$p){
    #select the city c' from the remaining S'
   while(($c_prime == $c) or ($c_prime == 9999)){   
    $c_prime = $temp_gene[int(rand($number_column))];
    #print"temp gene c prime : $c_prime\n";
   }
   
  }else{
      #select randomly an individual from P
           my @other_temp_gene = split /,/, ($population[int(rand($pop_size))]);
           #print "other temp gene: @other_temp_gene\n";
           #assign to c' the city next to the city c in the selected individual
           my $found_c_flag = 0; 
           my $c_counter=0;
           while($found_c_flag == 0 and $c_counter<$number_column){
            if($other_temp_gene[$c_counter] == $c ){
            $c_prime = $other_temp_gene[$c_counter+1];
             $found_c_flag=1;
             #print "other temp c prime: $c_prime\n";
            }
            $c_counter++;
           }
  }
  # if next or previous city of city c in S'is c'
  if ($temp_gene[$pos_c+1] == $c_prime or $temp_gene[$pos_c-1]==$c_prime){
           #print "goto Label\n";
      goto LABEL;#EXIT FROM REPEAT LOOP 
  }
  #inver next c to c'
  my $c_prime_positioner=0;
  while($pos_c_prime==9999){
      if($c_prime == $temp_gene[$c_prime_positioner]){
          $pos_c_prime=$c_prime_positioner;
      }
      $c_prime_positioner++;
  }
  my @seg;
  if ($pos_c<$pos_c_prime){
        @seg = @temp_gene[$pos_c+1..$pos_c_prime];    
        my @seg_temp = reverse @seg;
        for my $insert_index(0..$#seg_temp){
           $temp_gene[$pos_c+1+$insert_index]=$seg_temp[$insert_index];
          }  
  }else{
          @seg = @temp_gene[$pos_c_prime..$pos_c-1];
          my @seg_temp = reverse @seg;
          for my $insert_index(0..$#seg_temp){
           $temp_gene[$pos_c_prime+$insert_index]=$seg_temp[$insert_index];
          }
  }
  
  #c<-c'
  $c = $c_prime;
  }#REPEAT
  
  LABEL: my $final_temp_gene = join ",", @temp_gene;
  #print"gene: $gene\n";
  #print"final temp gene: $final_temp_gene\n";
  #sleep 15; 
  my $fitness_temp_gene     = fitness($final_temp_gene);
  my $fitness_gene         = fitness($gene); 
  if($fitness_temp_gene<$fitness_gene){#evalS'<evalS
   #print"swap here\n";
   $gene = $final_temp_gene;
  }
 }
}


sub fitness {
	#print "input $_[0]\n";
	my @input =  split /,/, $_[0];
	my $right_count = 0;
	for my $i(0..$#input){
		$right_count = $right_count + abs($input[$i]-$target[$i]);
	}
	if($right_count==0){
		print"here: $right_count\n";
		print"@input";
		exit;
	}
	
	return $right_count;
}
 
sub genotype {
 my @gene = shuffle 0 .. $number_column-1;
 return  join ",", @gene;
}