Think about how this is going to be implemented:
;; swap subtrees
(rotatef (get-random-subtree father)
(get-random-subtree mother))
The rotatef
form is going to be macro-expanded into something along the lines of this:
(let ((a (get-subtree father (random (descs father))))
(b (get-subtree mother (random (descs mother)))))
(setf (get-subtree father (random (descs father))) b)
(setf (get-subtree mother (random (descs mother))) a))
(You can use macroexpand
to find out exactly what the expansion is in your case.)
In other words, the random subtrees are going to be selected twice (once when reading and once when updating), so that instead of the subtrees being swapped with each other, references to the subtrees will be copied into random places in the other tree.
For example, in the diagram below, the algorithm might pick the blue and red subtrees to swap. But when it comes to attach them, it puts them at the points marked with dots.
The bottom half of the diagram shows the resulting data structure after the subtrees have been attached to the new points: you can see that a cycle has been created.
So you need to revise the code so that you can select the random subtrees just once. Something like this, perhaps:
(let ((a (random (descs father)))
(b (random (descs mother))))
(rotatef (get-subtree father a)
(get-subtree mother b)))