Kata

In genetic algorithms, a crossover allows 2 chromosomes to exchange part of their genes.

For more details, you can visit these wikipedia links : Genetic algorithm and Crossover.

A chromosome is represented by a list of genes.
Consider for instance 2 chromosomes :

   xs (with genes [x,x,x,x,x,x])  and  ys (with genes [y,y,y,y,y,y])

A single-point crossover at index 2 would give :

new chromosome1 = [x,x,y,y,y,y] and new chromosome2 = [y,y,x,x,x,x]

new chromosome1 = [x;x;y;y;y;y] and new chromosome2 = [y;y;x;x;x;x]

new chromosome1 = [x,x,y,y,y,y] and new chromosome2 = [y,y,x,x,x,x]

new chromosome1 = []int { x,x,y,y,y,y } and new chromosome2 = []int { y,y,x,x,x,x }

new chromosome1 = List(x,x,y,y,y,y) and new chromosome2 = List(y,y,x,x,x,x)

new chromosome1 = [x,x,y,y,y,y] and new chromosome2 = [y,y,x,x,x,x]

A two-point crossover at indices 1 and 3 would give :

new chromosome1 = [x,y,y,x,x,x] and new chromosome2 = [y,x,x,y,y,y]

new chromosome1 = [x;y;y;x;x;x] and new chromosome2 = [y;x;x;y;y;y]

new chromosome1 = [x,y,y,x,x,x] and new chromosome2 = [y,x,x,y,y,y]

new chromosome1 = []int { x,y,y,x,x,x } and new chromosome2 = []int { y,x,x,y,y,y }

new chromosome1 = List(x,y,y,x,x,x) and new chromosome2 = List(y,x,x,y,y,y)

new chromosome1 = [x,y,y,x,x,x] and new chromosome2 = [y,x,x,y,y,y]

We want to generalize this to the notion of n-point crossover, and create a generic function with the following signature :

crossover :: [Int] -> [a] -> [a] -> ([a],[a])
crossover ns xs ys = undefined

crossover : int list -> 'a list -> 'a list -> 'a list * 'a list
crossover ns xs ys = 

# crossover() takes a list of indices ns (integers) and 2 lists xs and ys
# It returns a tuple of lists: ([],[])
def crossover(ns, xs, ys) 

func Crossover(ns []int, xs []int,ys []int) ([]int, []int) 

 def crossover[T](ns: List[Int], xs: List[T], ys: List[T]): (List[T],List[T])

fn crossover(ns: &[usize], xs: &[u8], ys: &[u8]) -> (Vec<u8>,Vec<u8>)

where ns would be a list of cross-point indices.

We could compute a triple-point crossover of 2 chromosomes xs and ys the following way :

crossover [2,5,21] xs ys

crossover [2;5;21] xs ys

crossover([2,5,21], xs, ys) 

Crossover(int[] { 2, 5, 21 }, xs, ys) 

crossover(List(2,5,21), xs, ys) 

crossover(&[2,5,21], &xs, &ys);

The transformed first chromosome must appear at the first position of the tuple. the second one at the second position. Therefore :

(crossover [1] ['a','b','c'] ['x','y','z']) `shouldBe` (['a','y','z'],['x','b','c'])

(crossover [1] ['a';'b';'c'] ['x';'y';'z']) should be (['a';'y';'z'],['x';'b';'c'])

crossover([1],['a','b','c'],['x','y','z']) should be (['a','y','z'],['x','b','c'])

Crossover([]int { 1 }, []int {1,2,3}, []int {11,12,13}) should be ([]int { 1,12,13 }, int[] { 11,2,3 })

crossover(List(1),List('a','b','c'),List('x','y','z')) should be (List('a','y','z'), List('x','b','c'))

crossover(&[1], &[1,2,3], &[11,12,13]) should be (vec![1,12,13],vec![11,2,3])

If a cross-point index is repeated, it should be considered only once. Indices can also be provided unordered, so your function could be called with the following indices :

crossover [7,5,3,5] xs ys

crossover [7;5;3;5] xs ys

crossover([7,5,3,5], xs, ys) 

Crossover(int[] { 7,5,3,5 }, xs, ys) 

crossover(List(7,5,3,5), xs, ys)

crossover(&[7,5,3,5], &xs, &ys)

In this case, you would have to consider only indices [7,5,3] and deal with the fact they are unordered.

Chromosome indices are 0-based and you can also assume that :

1. (length xs) == (length ys)
2. crossover indices will never exceed the length of xs or ys.