I have a LISP exercise to propose:
"Generate all trees of size N and of depth H".
Example:
Binary tree -> size (N) = 2.
Here are the BINARY tree that the program would give for a depth value
of 1:
1)
0
/
0
2)
0
\
0
3)
0
/ \
0 0
So the DEFUN of the lisp program would be something like this:
(defun tree (N H) ...
where N is the size of the tree (binary=2, trinary=3, quaternary=4,
etc.) and where H is the depth of the tree (1,2,3,4,etc.). It is evident
that at the moment you'll arrive at depth of 3 and higher, the function
will take very long to execute since there will be so many
possibilities.
So I suggest limiting the function testing to a depth of 3. And don't go
to high on the tree size too (trinary, quaternary maximum). But the
program has to be able to generate the trees for higher values of H and
N.
Thank you !
···········@yahoo.com
"Rock Stone 99" wrote:
> I have a LISP exercise to propose:
You mean "I have an exercise I was set as homework, and I want
to fool you guys into doing it for me". Someone else was in c.l.l
recently with the same problem (clearly from the same source --
identical non-obvious choices of notation), but he was honest
enough to admit it was an exercise *he* had been set.
You will get a much more friendly response to "help me with my
homework, please" requests if you are honest.
> where N is the size of the tree (binary=2, trinary=3, quaternary=4,
> etc.) and where H is the depth of the tree (1,2,3,4,etc.). It is evident
> that at the moment you'll arrive at depth of 3 and higher, the function
> will take very long to execute since there will be so many
> possibilities.
Doing it with n=4, h=3 takes my machine all of 1.8 seconds.
--
Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
·····@dpmms.cam.ac.uk Cambridge University, England.
OK, I admit it. This is a homework. The only problem: nobody in the class has
been able to do anything good so far. We're not all stupid, damn it ! The
bigest part of the problem is that we're supposed to do something very
complicated based on the very small amount of lisp we've been teached.
I wasn't aware that someone else did post something before me.
So if you can help me, I would appreciate it.
I am sorry for the ones who think I was trying to fool them.
Thanks.
Gareth McCaughan wrote:
> "Rock Stone 99" wrote:
>
> > I have a LISP exercise to propose:
>
> You mean "I have an exercise I was set as homework, and I want
> to fool you guys into doing it for me". Someone else was in c.l.l
> recently with the same problem (clearly from the same source --
> identical non-obvious choices of notation), but he was honest
> enough to admit it was an exercise *he* had been set.
>
> You will get a much more friendly response to "help me with my
> homework, please" requests if you are honest.
>
> > where N is the size of the tree (binary=2, trinary=3, quaternary=4,
> > etc.) and where H is the depth of the tree (1,2,3,4,etc.). It is evident
> > that at the moment you'll arrive at depth of 3 and higher, the function
> > will take very long to execute since there will be so many
> > possibilities.
>
> Doing it with n=4, h=3 takes my machine all of 1.8 seconds.
>
> --
> Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
> ·····@dpmms.cam.ac.uk Cambridge University, England.
In article <·················@yahoo.com>,
Rock Stone 99 <···········@yahoo.com> writes:
> OK, I admit it. This is a homework. The only problem: nobody in the class has
> been able to do anything good so far. We're not all stupid, damn it ! The
> bigest part of the problem is that we're supposed to do something very
> complicated based on the very small amount of lisp we've been teached.
> ...
How about you start with your thoughts on the problem and let us know where
you got stuck? That would be a good starting point.
Rock Stone 99 <···········@yahoo.com> writes:
> I have a LISP exercise to propose:
>
> "Generate all trees of size N and of depth H".
_Exactly_ what output do you expect from this program?
Stig Hemmer,
Jack of a Few Trades.
I expect an output like that:
TREE:
0
/ \
0 0
Of course, this is a one possibility of binary tree of height 2. The
output would have the form of a list (of course...we are programming in
LISP). For example, the preceding tree would be represented like that:
( (0 0) (0 0) )
where (00) represents a node that has no children.
The tree
0
/
0
would have that output:
( (0 0) nil )
The tree
0
/ \
0 0
/
0
would have this output:
( ( (0 0) nil) (0 0) )
---------- ----
| |
Left Right
where the right side is reprsented by (0 0)
and the left side by ( (0 0) nil ).
Thaks for adressing my question. I would really appreciate some help.
···········@yahoo.com
Stig Hemmer wrote:
> Rock Stone 99 <···········@yahoo.com> writes:
> > I have a LISP exercise to propose:
> >
> > "Generate all trees of size N and of depth H".
>
> _Exactly_ what output do you expect from this program?
>
> Stig Hemmer,
> Jack of a Few Trades.
This article contains very little Lisp, but a more general discussion
of the problem. You'll have to write the Lisp yourself. However, I'm
thinking Lisp as I write this, so that the task should be managable.
I'm not trying to be efficient here, if you call the resulting program
with too large N and H, it will take _very_ long to run...
It is generally best to write a programs as a lot of small DEFUNs,
rather than a few large ones. The result is much easier to read, and
much easier to test for bugs.
Rock Stone 99 <···········@yahoo.com> writes:
...
> (0 0)
...
> where (00) represents a node that has no children.
...
Be aware that (0 0) and (00) are two different things. I do think you
have probably misread this part of your excerise text. However, the
main point is that there one and only depth-0 tree, regardless of how
you represent it.
Now, a tree of depth N is a tree with children of depth at most N-1,
where at least one of the children has the exact depth N-1.
Ugh. That was ugly. Not too easy to program. (Though by no means
impossible)
Hmm... the definition of "tree of depth at most N" is much easier: A
tree of depth at most N is a tree with children of depth at most N-1.
That was simpler, right?
Now, a "tree of depth exactly N" is nothing but a "tree of depth at
most N", which is NOT a "tree of depth at most N-1".
So, what you need to do is to generate
- all the trees of depth at most 0 (there is only one)
- all the trees of depth at most 1
- ... 2
Until you reach the N you want. You need to keep a list of all the
trees you generate along the way. Each time you generate a new tree,
you check to see if it is already on the list. If it isn't, add it.
(Don't mind the screams, that is just the experienced Lisp programmers
thinking about how inefficient this is)
When you reach N, every NEW tree you see, is a tree of depth exactly N
and should be part of the output of your program.
Right, that should do it.
Well, almost. I sort of skipped the part where you generated the
trees, didn't I? Indeed I did.
A tree is nothing but a list of its children. You want to generate
all possible lists with H elements, with the elements chosen among the
possible children.
Well... a H-element list is just an element added to a (H-1)-element
list. (It is better to add the new element at the _front_ of the
list)
So, you just start by
- generating all possible 0-element lists, there is just one, NIL.
- generating all possible 1-element lists, which is all possible elements
added to all possible 0-element lists
- ... 2 ...
Did that help a bit?
Stig Hemmer,
Jack of a Few Trades.
I guess it will help us a little.
Thanks for your help.
Stig Hemmer wrote:
> This article contains very little Lisp, but a more general discussion
> of the problem. You'll have to write the Lisp yourself. However, I'm
> thinking Lisp as I write this, so that the task should be managable.
>
> I'm not trying to be efficient here, if you call the resulting program
> with too large N and H, it will take _very_ long to run...
>
> It is generally best to write a programs as a lot of small DEFUNs,
> rather than a few large ones. The result is much easier to read, and
> much easier to test for bugs.
>
> Rock Stone 99 <···········@yahoo.com> writes:
> ...
> > (0 0)
> ...
> > where (00) represents a node that has no children.
> ...
>
> Be aware that (0 0) and (00) are two different things. I do think you
> have probably misread this part of your excerise text. However, the
> main point is that there one and only depth-0 tree, regardless of how
> you represent it.
>
> Now, a tree of depth N is a tree with children of depth at most N-1,
> where at least one of the children has the exact depth N-1.
>
> Ugh. That was ugly. Not too easy to program. (Though by no means
> impossible)
>
> Hmm... the definition of "tree of depth at most N" is much easier: A
> tree of depth at most N is a tree with children of depth at most N-1.
> That was simpler, right?
>
> Now, a "tree of depth exactly N" is nothing but a "tree of depth at
> most N", which is NOT a "tree of depth at most N-1".
>
> So, what you need to do is to generate
> - all the trees of depth at most 0 (there is only one)
> - all the trees of depth at most 1
> - ... 2
>
> Until you reach the N you want. You need to keep a list of all the
> trees you generate along the way. Each time you generate a new tree,
> you check to see if it is already on the list. If it isn't, add it.
> (Don't mind the screams, that is just the experienced Lisp programmers
> thinking about how inefficient this is)
>
> When you reach N, every NEW tree you see, is a tree of depth exactly N
> and should be part of the output of your program.
>
> Right, that should do it.
>
> Well, almost. I sort of skipped the part where you generated the
> trees, didn't I? Indeed I did.
>
> A tree is nothing but a list of its children. You want to generate
> all possible lists with H elements, with the elements chosen among the
> possible children.
>
> Well... a H-element list is just an element added to a (H-1)-element
> list. (It is better to add the new element at the _front_ of the
> list)
>
> So, you just start by
> - generating all possible 0-element lists, there is just one, NIL.
> - generating all possible 1-element lists, which is all possible elements
> added to all possible 0-element lists
> - ... 2 ...
>
> Did that help a bit?
>
> Stig Hemmer,
> Jack of a Few Trades.