We were asked to create a program that would list all possible trees of
dimension N for a given height H. Of course we had no problem for a tree
of dimension 0 and 1 for any given height but for a binary tree and
bigger we are stuck. We can easily create a binary tree. But we can
seem to be able to list all possibilities. We chose to represent a
tree as follow: (0(0 0)) --- (0(0(0 0 0)0 0)) Which represent ->
0 0
/\
/|\
0 0 0 0 0
/|\
000
So for a tree of dimension two (binary tree and an height of 1, the
program should list the following:
(0(0 0))
(0(0 nil))
(0(nil 0))
Now, we beleive that the way we represent a tree as little importance
(but maybe we are wrong), the algorithms and the way we create our
functions and call them is important. But we have checked everywhere
and have learn a lot about Lisp but we still are nowhere near doing
something that make sense. As anyone have an idea of how we should do
it??
Thanks for the help...
Simon Pageot wrote:
> We were asked to create a program that would list all possible trees of
> dimension N for a given height H.
You have, I presume, some definition of the form "An N-ary tree of
height <=H is either an empty tree, or (if H>=1) a sequence of N
N-ary trees of height <= H-1". (I don't know exactly what
the course you're doing uses as its definition, but it will be
something like that.)
Well, turn that into a recursive definition: "The list of all N-ary
trees of height <= H consists of the empty tree, plus the list of
all trees formed as sequences of [etc]".
It shouldn't be difficult to turn this into a recursive function
to produce the list of all binary trees. You'll need to be able to
produce, given a list of trees, a new list containing all trees
that can be obtained by joining N of the trees in the list.
(Or, if your definition of "N-ary tree" is a little different,
you might need to replace "by joining N of the trees" with
"by joining <= N of the trees" or something.)
I recommend doing this with a separate function, which will also
be recursive. This time the rule will be something like: "The list
of all 0-sequences from list L is (obviously) the list containing
only the empty sequence. The list of all (N+1)-sequences from list
L is the list of all sequences consisting of something from L, followed
by one of the N-sequences from L". (Got that?)
This won't be quite the same as what you need, given the representation
you've chosen for your trees; but it's close enough that, given the
list of such sequences, you can easily form the list of trees that
you actually want. (Easiest way: use MAPCAR.)
I suspect this is all too vague to be of much use to you, but I'm
not sure how I can go into more detail without doing your homework
for you; that would be a Bad Idea, because you'll learn much more
from doing it yourself...
--
Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
·····@dpmms.cam.ac.uk Cambridge University, England.
Gareth McCaughan wrote:
> Simon Pageot wrote:
>
> > We were asked to create a program that would list all possible trees of
> > dimension N for a given height H.
>
> You have, I presume, some definition of the form "An N-ary tree of
> height <=H is either an empty tree, or (if H>=1) a sequence of N
> N-ary trees of height <= H-1". (I don't know exactly what
> the course you're doing uses as its definition, but it will be
> something like that.)
>
Well, yes that would be the definiton, one of my main problem and pretty much
everybody else in our class is that this assignement was given in a course on
programming language, which we learn about LISP, ML and ADA. We only had 6
hours on Lisp and my team and I have already log on close to 40 hours on this
assignement and all we have that is functional is the following:
(defun arbre (n h)
(cond
((= n 0) (cons nil nil))
((= h 0) (cons 0 nil))
((= n 1) (let ((tree (cons '(nil) nil)))
(while (> h 0)
(setq tree (cons '(0) tree))
(setq h (1- h))
)))
))
We are not looking for an answer but Lisp is a language which we are not
accustomed with and we can seem to get the necessary recursion down, at the
moment we are trying to do the same exercise using C++, since this is the
language used through out most of our courses. From what I gather once I
create a function that define n-tree of h=1, for h= 2 all I have to do is add
a node and recall the function for level one tree for each node and so on .
But where could we find additional example on Lisp and the use of recursion in
lisp?? Or a least additional hints, we would be grateful since this is the
only assignement for that class (Is in it weird?One assignement for a whole
semester based on matter seen in 2 classes out of 15!)
Thanks
Simon
In article <··············@g.pet.cam.ac.uk> , Gareth McCaughan
<·····@dpmms.cam.ac.uk> wrote:
[snip]
> There are some books that cover the subject reasonably well.
> There's an on-line book, partially written, by David Lamkins;
> I don't remember exactly where it's located, but I think there's
> been an article in c.l.l about it within the last month...
<http://www.teleport.com/~dlamkins/sl/sl.html>
[snip]
--
David B. Lamkins <http://www.teleport.com/~dlamkins/>
((lambda (x) (list x (list 'quote x)))
'(lambda (x) (list x (list 'quote x))))