I'm implementing an evolutionary algorithm in Common Lisp (CLISP) and I have a problem.

I have a tree-like class:

```
(defclass node ()
((item :initarg :item :initform nil :accessor item)
(children :initarg :children :initform nil :accessor children)
(number-of-descendants :initarg :descs :initform nil :accessor descs)))
```

And some methods:

```
(defmethod copy-node ((n node))
(make-instance
'node
:item (item n)
:descs (descs n)
:children (mapcar #'copy-node (children n))))
(defmethod get-subtree ((n node) nr)
(gsth (children n) nr))
(defmethod (setf get-subtree) ((val node) (n node) nr)
(setf (gsth (children n) nr) val))
(defmethod get-random-subtree ((n node))
(gsth (children n) (random (descs n))))
(defmethod (setf get-random-subtree) ((val node) (n node))
(setf (get-subtree n (random (descs n))) val))
(defun gsth (lst nr)
(let ((candidate (car lst)))
(cond
((zerop nr) candidate)
((<= nr (descs candidate)) (gsth (children candidate) (1- nr)))
(t (gsth (cdr lst) (- nr (descs candidate) 1))))))
(defun (setf gsth) (val lst nr)
(let ((candidate (car lst)))
(cond
((zerop nr) (setf (car lst) val))
((<= nr (descs candidate))
(setf (gsth (children candidate) (1- nr)) val))
(t (setf (gsth (cdr lst) (- nr (descs candidate) 1)) val)))
val))
```

What I'm trying to do is to swap two random subtrees of two random trees from the population. But when I do something like this:

```
(defun stdx (population)
(let ((n (length population))
(npop))
(do ((done 0 (+ done 2)))
((>= done n) npop)
(push (stdx2 (copy-node (random-el population))
(copy-node (random-el population)))
npop))))
(defun stdx2 (father mother)
;; swap subtrees
(rotatef (get-random-subtree father)
(get-random-subtree mother))
(check-for-cycles father)
(check-for-cycles mother))
```

Sometimes a cycle is detected, which obviously shouldn't take place.

Check-for-cycles is OK, I detected cycles with (trace) too. I keep number-of-descendants updated all the time.

I guess something is wrong with (setf get-subtree). I'm new to LISP and I'm not very good with setf expansion. Please help me.

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)))
```

Similar Questions

Is there a way to remove a scope from the digest cycles? In other words, to suspend/resume a scope digest cycle? In my case, I have all pages already loaded, but not all of them visible. So I'd like t

I was wondering if there was a possibility to let a thread sleep for a certain amount of CPU-cycles? I thought about just inserting nop's but I'm not sure if they get optimized away and I was hoping

I want to find all cycles in a graph that is built organically. In a nutshell cycles happen when two branches or paths end at a common vertex. Something like 1->2->3->4 1->5->4 form the

i got a tree <rich:tree acceptedTypes=menu> <rich:treeNode dragType=menu acceptedTypes=menu,article> menu </rich:treeNode> <rich:treeNode dragType=article acceptedTypes=n

I have a directed graph and my problem is to enumerate all the minimal (cycles that cannot be constructed as the union of other cycles) directed cycles of this graph. This is different from what the T

I know I can do the following in Common Lisp: CL-USER> (let ((my-list nil)) (dotimes (i 5) (setf my-list (cons i my-list))) my-list) (4 3 2 1 0) How do I do this in Clojure? In particular, how do

Using objgraph, I found a bunch of objects like this: Will Python's garbage collector deal with cycles like this, or will it leak? A slightly wider view of the loop:

I have an application where I need to access model data from my subviews. I've been using bindings to pass data across views; however, the bindings to self seem to be causing retain cycles (dealloc ne

How many clock cycles does these fours instructions take? #Macro Instructions li $t0, 32 # 1 or 2 cycles ? # # Based on MIPS Assembly Language Programming by Robert Britton : # # lui $at, Upper 16-bit

I need some help in understanding the difference between regression trees and linear model tree. Regards Shahzad

I'm back with another similar question. I am currently working on a Java program that will check if a graph is 2-colorable, i.e. if it contains no odd cycles (cycles of odd number length). The entire

I have a jface tree without columnviewer support. It has a decorating label provider as i need to decorate the tree items. I cannot use a celllableprovider to do this. I have seen the examples such as

i have to Find the longest path in a directed cyclic graph from a source s to a destination f. Assume no positive weight cycles exists even though no positive weight cycles exist, cycles of 0 or negat

Suppose that I have a function represented in LLVM IR and I want to estimate the number of cpu cycles that this function would take on my machine. I know this is an information which is specific to t

How wil you convert Binary Tree to Binary Search Tree with O(1) extra space ?

What's a B*Tree? Did they just mean binary search tree?

I'm getting the error: Object graph for type 'System.Collections.Generic.List`1[[Proj.Model.Prom, Proj.Model, Version=1.0.0.0, Culture=neutral, PublicKeyToken=null]]' contains cycles and cannot be se

My code for calculating clock cycles for creating thread is # include <Windows.h> # include <stdio.h> # include <conio.h> # define RUN 20000 DWORD WINAPI Calc(LPVOID Param){} int ma

How can I refactor the following code: class ModifyTree{ public void doActionsOnTree(Tree tree) { rAction1(tree.getRoot()); rAction2(tree.getRoot()); } private void action1(Node node) { // do somethin

I'm interested in hearing how WebWorks developers are saving time during their development cycles by using any clever build processes / testing techniques. What tips & tricks would you recommend

I have created a very simple example showing an issue I have encountered on a much more complicated query using dynamic SQL and I can't figure out why the CTE is causing the error when the standard ve

I have successfully imported a model that I have created materials in Blender using Blender Internal Engine. However, I was not successful doing so with the items created in Cycles. I was following a

Please explain the difference between a binary search tree and m-way tree?

The following code: s = s.replace(u&, u&) is causing an error in python: SyntaxError: invalid syntax removing the u's before the fixes the problem, but this should work as is? I'm

I want to detect cycles in an undirected graph such that I can find the minimum spanning tree (in particular I want to use Kruskal algorithm). Since I want to parallelize the code, I was wondering whi

I am having a hard time understanding clock cycles. Here is the problem, I am given a program that has two instructions X and Y and I know that X is run 20% of the time and requires 8 clock cycles and

What are Splay tree, Red-black tree, AVL tree, B-tree and T-tree? I'm looking for good implementations.

How do you prevent agile methodology with monthly sprints/iterations causing a fragmented design. For ex. take the case of design of Manhattan Streets vs Design of Boston streets. The blueprints for M

I need a general formula to calculate the minimum height of the binary tree and the maximum height of the binary tree. (not the binary search tree)

We've been using Lisp in my AI course. The assignments I've received have involved searching and generating tree-like structures. For each assignment, I've ended up writing something like: (defun init

I am trying to create a copy constructor for my Binary tree. My problem: I can see the values of the source tree getting copied into the traget tree but when it comes to writing the values out, there

given bin tree defn : // a binary tree node case class Node( var data:(Int), left:Option[Node], right:Option[Node] ) I need to get the in order tree traversal of the binary tree. for eg: val testtre

What would be a major reasons to prefer R+-Tree over R-Tree for a spatial indexing? As I know, R+-Tree avoid nodes overlapping which lead to more complex code, more complex division algorithms and so

*mit = 13311 std::istringstream iss(*mit); double temp; iss.setf(ios::fixed, ios::floatfield); iss.precision(15); iss >> temp; std::cout<<temp <<temp<<endl; std::stringstream

Reference counting alone does not collect cycles but there are additional techniques that can collect cycles as well. What is the simplest such technique? I'd like to compare the complexity of augment

Let's say I have a lazy Tree whose leaves are possible solutions to a problem data Tree a = Node [Tree a] | Leaf (Maybe a) I need to find just one solution (or find out that there are none). I have a

just another slight problem. I must also create an equals method for my IntTree class which cycles through two tree's and compares the nodes. If all of the values in the tree are equal, then it return

I have created a directed graph in Haskell. I would like to write an algorithm that checks the graph for cycles. Are there library functions available that could do this quickly?

#include <iostream> using namespace std; int main() { double pi = 0.1234567; cout << 1234567890 << endl; // cout.width(10); cout.setf(ios::fixed); cout << pi << endl; }

i wanna make a dynamic tree using a lazy loading ,each time i open a folder the tree sends a http request to the server, in this script i'm using just static text to test the tree but , i'm getting in

suppose there is a tree with number of child nodes increasing from 2 to 4 then 8 and so on.how can we write recurrence relation for such a tree.

I have graphs with thousands of nodes to millions of nodes. I want to detect all possible cycles in such graphs. I use hash table to store the edges. ( (source node,edge weight) -> (target node) )

I'm having problems with a bit of code I've written that cycles through an array of ads. The render function gets called on an interval (configurable, but set to every 50ms to help with debugging). Th

I want to write a function load: 'a option list -> 'a tree, that restores binary tree from the given list, which contains the elements in postfix order. If the list does not represent any tree, you

I am developing a Tree component, which might be prunned according to the user input. I have all nodes cached, in order to provide primefaces component model with always the same instances of the tree

Is there an equivalent to tree on CentOS?

I'm trying to make my own tree class but keep getting horribly confused. Basically I'm trying to make a weighted tree. I've made the following node class: import java.util.*; public class subdivNode

For a homework assignment I wrote some scala code in which I have the following classes and object (used for modeling a binary tree): object Tree { def fold[B](t: Tree, e: B, n: (Int, B, B) => B):

how can I build a balanced quad tree. Thanks, Marcos

I'm looking for a way to represent a family tree (family tree is an elaborate metaphor) in PHP. This means that children will need to inherit from two (or more) parents. Here are the requirements: