I'm writing a Genetic Algorithm, and need to write a function that crosses two gene sequences. Basically, I want it to work like this:
(running-cross [1 2 3 4 5 6 7 8 9] ; Gene sequence 1
[11 22 33 44 55 66 77 88 99] ; Gene sequence 2
[2 5]) ; The "cross points"
=> [1 2 33 44 55 6 7 8 9]
Note how it crosses over to the second sequence at index 2
, and back to the first sequence at index 5
. See the related PPCG challenge for more examples.
I have two main concerns with my implementation:
It's ugly. The reducing function is atrocious, but I don't know what can be improved. The short names don't help, but longer names would add significant bloat which wouldn't be great either.
It's inefficient. It requires iterating the entire gene sequence, even if there are few, or even no cross over points. Of course I could add a special case and check if the points are empty first, but that still doesn't help much. Say there's a single cross over point at the end of the genes. It will require a full iteration regardless. I can't tell if
O(n)
is the best I'm going to get, but I'd prefern
be the number of cross-over points, not the number of genes per sequence.
(defn running-cross [genes other-genes cross-points]
(let [cp-set (set cross-points)]
(->> (map vector (range) genes other-genes)
(reduce (fn [[g1? acc] [i g1 g2]]
(let [g1?' (if (cp-set i) (not g1?) g1?)]
[g1?' (conj acc (if g1?' g1 g2))]))
[true []])
(second))))