# File lib/charlie/permutation/permutation.rb, line 98
 98:   def cross(parent1,parent2)
 99:     p1, p2 = parent1.genes, parent2.genes
100:    
101:     nb = Array.new(parent1.size){[]}
102:     (p1 + p1[0..1]).each_cons(3){|l,m,r| nb[m] += [l,r] } # build neighbour lists
103:     (p2 + p2[0..1]).each_cons(3){|l,m,r| nb[m] += [l,r] } # build neighbour lists
104:     nb.map(&:uniq!)
105: 
106:     n = (rand < 0.5 ? p1.first : p2.first)
107:     child = [n]
108:     (nb.size-1).times{
109:       nb.each{|l| l.delete n unless l==:done }  # remove n from the lists
110: 
111:       if nb[n].empty?  # nb[n] empty, pick random next
112:         nb[n] = :done
113:         n = (0...nb.size).find_all{|x| nb[x] != :done }.at_rand # no neighbors left, pick random
114:       else # pick neighbour with minimal degree, random tie-breaking
115:         min_deg = nb[n].map{|x| nb[x].size }.min
116:         next_n = nb[n].find_all{|x| nb[x].size == min_deg }.at_rand # pick random neighbor with min. degree
117:         nb[n] = :done
118:         n = next_n
119:       end 
120:       child << n  # add new n to path
121:     }
122:     
123:     return from_genes(child)
124:   end