Tree manipulation
Julian St.
First thanks for the fast help with my string parsing problem. But although my
common lisp experience is growing, now I got another one:
If there is a tree-like list (hey every lisp expression is somehow a tree *g*)
like
(* (+ 1 (/ 5 3)) 3) how would I choose a random node and alter it?
I could think of a recursive method, but as I dont know the deepness of the
tree in advance it is very likely to end up with nodes that are not equally
spread over the whole tree.
Useful nodes would be every one except the root itself e.g. (+ 1 (/ 5 3)) or
just 3.
This is no homework, but I am very curious about that topic.
Gruss
Julian
--
Zum Antworten via Mail .nospam in der ElektroPost (eMail fuer die Neudeutschen)
Adresse entfernen.
(To reply simply remove .nospam in my email address.)
Kent M Pitman
> If there is a tree-like list [...] (* (+ 1 (/ 5 3)) 3) how would I choose
> a random node and alter it? I could think of a recursive method, but as I
> dont know the deepness of the tree in advance it is very likely to end up
> with nodes that are not equally spread over the whole tree. Useful nodes
> would be every one except the root itself e.g. (+ 1 (/ 5 3)) or just 3.
This is a pretty bizarre thing to want to do, but if you really mean it, then
I would probably write a function that counts the conses in the tree and then
another that, given a number, finds the nth cons by tree-walking. Something
like
(defun count-conses (tree)
(cond ((consp tree)
(+ 1
(count-conses (car tree))
(count-conses (cdr tree))))
(t 0)))
(defun nth-cons (tree n)
;; Returns either the nth cons or, if there were not n conses, the number
;; of conses still to be looked through elsewhere.
(cond ((consp tree)
(cond ((<= n 0) tree)
(t
(let ((car-try (nth-cons (car tree) (- n 1))))
(cond ((consp car-try) car-try)
(t (nth-cons (cdr tree) car-try)))))))
(t n)))
(defun random-cons (tree)
(nth-cons tree (random (count-conses tree))))
To avoid getting the root, I suppose you'd just do:
(defun random-cons (tree)
(nth-cons tree (1+ (random (1- (count-conses tree))))))
though it's worth adding some error checking for no conses being given.
[I didn't do that.]
p.s. I only tested this very lightly since I only had a couple of spare
minutes to spend on it.
Julian St.
<pit...@world.std.com> schreibt:
>> If there is a tree-like list [...] (* (+ 1 (/ 5 3)) 3) how would I choose
>> a random node and alter it? I could think of a recursive method, but as I
>> dont know the deepness of the tree in advance it is very likely to end up
>> with nodes that are not equally spread over the whole tree. Useful nodes
>> would be every one except the root itself e.g. (+ 1 (/ 5 3)) or just 3.
>
>This is a pretty bizarre thing to want to do, but if you really mean it, then
>I would probably write a function that counts the conses in the tree and then
>another that, given a number, finds the nth cons by tree-walking.
Sounds good. I'll try to implement it. Thanks.
Frank A. Adrian
dfs traversal counting the nodes. Then you select a random number k,
0<=k<n, where n is the number of nodes found. Finally, write a function
that does a simple dfs traversal to node k and change the one you land on.
If you're looking for example code that looks something like this, you might
check out Koza's book on Genetic Programming. As I recall, his crossover
operator selects a pair of subnodes a random from two expression trees and
swaps them. His mutation operator replaces a random node with a randomly
generated replacement. All of this is done in this manner. Of course, you
can work on more efficient code, keeping the number of nodes in the
expression as a part of the expression structure.
faa
"Julian St." <boel...@aol.com.nospam> wrote in message
news:20010406111705...@nso-cm.aol.com...
Julian St.
<fad...@uswest.net> schreibt:
>The simplest way would be to build a count-nodes function that did a simple
>dfs traversal counting the nodes. Then you select a random number k,
>0<=k<n, where n is the number of nodes found. Finally, write a function
>that does a simple dfs traversal to node k and change the one you land on.
Yes. I did it that way. But I find it difficult to change the node I found,
because I use recursion to walk the tree. I end up with the node as parameter
of a function. And ... how to go on?
>If you're looking for example code that looks something like this, you might
>check out Koza's book on Genetic Programming.
The theory is not the problem. The tree manipulation is ;)
Kent M Pitman
> Im Artikel <7Htz6.2422$Wj5.3...@news.uswest.net>, "Frank A. Adrian"
> <fad...@uswest.net> schreibt:
>
> >The simplest way would be to build a count-nodes function that did a simple
> >dfs traversal counting the nodes. Then you select a random number k,
> >0<=k<n, where n is the number of nodes found. Finally, write a function
> >that does a simple dfs traversal to node k and change the one you land on.
>
> Yes. I did it that way. But I find it difficult to change the node I found,
> because I use recursion to walk the tree. I end up with the node as parameter
> of a function. And ... how to go on?
Did you *read* the code I sent? It was a completely worked solution.
Julian St.
<pit...@world.std.com> schreibt:
>Did you *read* the code I sent? It was a completely worked solution.
hmm Somehow I overread it or my newsreader cut it off (very unlikely indeed
*g*).
Thanks.
-
Julian St.
>Did you *read* the code I sent? It was a completely worked solution.
Just tried your code. Works fine, but it does not the action I need. It returns
random conses (just as the name states) , but I need random nodes. The
difference is the following:
(random-cons '(* (+ 1 2) 3)) returns sometimes e.g. ((+ 1 2) 3). But that are 2
nodes.
Or (1 2). Valid values for a function named random-node would be (+ 1 2), 1, 2,
3, as these are the nodes of the tree:
*
/ \
+ 3
/ \
1 2
Kent M Pitman
> Im Artikel <sfw66gf...@world.std.com>, Kent M Pitman
> <pit...@world.std.com> schreibt:
>
> >Did you *read* the code I sent? It was a completely worked solution.
>
> Just tried your code. Works fine, but it does not the action I need. It returns
> random conses (just as the name states) , but I need random nodes. The
> difference is the following:
>
> (random-cons '(* (+ 1 2) 3)) returns sometimes e.g. ((+ 1 2) 3). But that are 2
> nodes.
> Or (1 2). Valid values for a function named random-node would be (+ 1 2), 1, 2,
> 3, as these are the nodes of the tree:
>
> *
> / \
> + 3
> / \
> 1 2
I see what you mean. But the program I used is completely general to
this kind of modification. It should be very easy to change what I
wrote to suit you. You just need to change car/cdr style descent into
map-style descent.
However, I'm going to leave that as an exercise for you because it's
my belief that if you understood the program, you would see how trivial
this is, and if you don't see how trivial it is, you need to study some
paradigms by first-hand trying them, not ask others to do it for you.
The difference between car/cdr descent and map-style descent is the
following:
one descends by first doing car then doing cdr.
the other maps a common descender over each of the useful nodes.
consider:
(defun my-subst-1 (new old tree)
(cond ((eq tree old) new)
((atom tree) tree)
(t (cons (my-subst-1 new old (car tree))
(my-subst-1 new old (cdr tree))))))
vs
(defun my-subst-2 (new old list)
(cond ((eq list old) new)
((atom list) list)
(t
(mapcar #'(lambda (sublist) (my-subst-2 new old sublist)) list))))
Consider the difference in behavior between
(my-subst-1 'a 'nil '(a b c)) => (A B C . A)
and
(my-subst-2 'a 'nil '(a b c)) => (A B C)
Of course, your problem isn't doing subst and you're treating the car of the
form specially, so you'll need additional changes to the above recursion
styles. But hopefully this will at least get you thinking.