Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: Plotting a recursion tree

• To: mathgroup at smc.vnet.net
• Subject: [mg108065] Re: [mg108010] Plotting a recursion tree
• From: Leonid Shifrin <lshifr at gmail.com>
• Date: Sun, 7 Mar 2010 05:09:17 -0500 (EST)
• References: <201003050932.EAA29345@smc.vnet.net>

Hi Bill,

First of all, what you create is not really a tree, in a sense that there
are no clear parent-children relationships between elements of your tree on
different levels. It is more like a result of collecting the nodes of the
real tree during the breadth-first traversal.

Here is what I woulld do (this is just one of the many possibilities):

Clear[makeMyTree, displayMyTree];
Module[{h},
  makeMyTree[a_Integer?Positive, b_Integer?Positive, x_,
    depth_Integer?Positive] :=
   Nest[# /. h[z_] :> {z, Table[h[z/b], {a}]} &, {h[x]}, depth] /.
    h -> Sequence ];

displayMyTree[tree_] :=
  TreeForm[
   Apply[Sequence,
     tree //. {c_, d_List} :> c @@ d] /.
    x_Times :> ToString@TraditionalForm@x];

You use this as follows:

In[4]:= makeMyTree[4, 2, x, 3]

Out[4]= {{x, {{x/
    2, {{x/4, {x/8, x/8, x/8, x/8}}, {x/4, {x/8, x/8, x/8, x/8}}, {x/
      4, {x/8, x/8, x/8, x/8}}, {x/4, {x/8, x/8, x/8, x/8}}}}, {x/
    2, {{x/4, {x/8, x/8, x/8, x/8}}, {x/4, {x/8, x/8, x/8, x/8}}, {x/
      4, {x/8, x/8, x/8, x/8}}, {x/4, {x/8, x/8, x/8, x/8}}}}, {x/
    2, {{x/4, {x/8, x/8, x/8, x/8}}, {x/4, {x/8, x/8, x/8, x/8}}, {x/
      4, {x/8, x/8, x/8, x/8}}, {x/4, {x/8, x/8, x/8, x/8}}}}, {x/
    2, {{x/4, {x/8, x/8, x/8, x/8}}, {x/4, {x/8, x/8, x/8, x/8}}, {x/
      4, {x/8, x/8, x/8, x/8}}, {x/4, {x/8, x/8, x/8, x/8}}}}}}}

In[5]:=
displayMyTree@makeMyTree[4, 2, x, 3]

(* Output suppressed. *)

Hope this helps.

Regards,
Leonid




On Fri, Mar 5, 2010 at 1:32 AM, metobillc <metobillc at gmail.com> wrote:

> Hello,
>
>  I'd like to be able to plot recursion trees, e.g. if I have a
> recurrence relation T(n) = 4T(n/2) + c n^2, T(1) = d (for integer n),
> and I want to plot T(8), I'd like to see a tree with 64 c at the head,
> 4 children with 16 c, 16 grandchildren with 4 c, 64 great granchildren
> with d (they are the leaves of the tree).  The best I've come up with
> so far is:
>
> mylist[a_Integer /; a > 0, b_Integer /; b > 0, x_, depth_Integer /;
> depth > 0] := NestList[Table[#/b, {a}] &, x, depth]
>
> mylist[4,2,x,3] yields
> {x,
> {x/2, x/2, x/2, x/ 2},
> {{x/4, x/4, x/4, x/4}, {x/4, x/4, x/4, x/4}, {x/4, x/4, x/4, x/4}, {x/
> 4, x/4, x/4, x/4}}, {{{x/8, x/8, x/8, x/8}, {x/8, x/8, x/8, x/8}, {x/
> 8, x/8, x/8, x/8}, {x/8, x/8, x/8, x/8}},
>  {{x/8, x/8, x/8, x/8}, {x/8, x/8, x/8, x/8}, {x/8, x/8, x/8, x/8}, {x/
> 8, x/8, x/8, x/8}},
>  {{x/8, x/8, x/8, x/8}, {x/8, x/8, x/8, x/8}, {x/8, x/8, x/8, x/8}, {x/
> 8, x/8, x/8, x/8}},
>  {{x/8, x/8, x/8, x/8}, {x/8, x/8, x/8, x/8}, {x/8, x/8, x/8, x/8}, {x/
> 8, x/8, x/8, x/8}}}}
>
> How can I get a separate case for the leaves, and then plot a list
> like this in tree form?  TreeForm[mylist[4,2,x,3]] has a bunch of
> nodes called "List" and "Times", and is not symmetric -- I just want
> the elements of the list.
>
> Thanks,
>
> Bill Campbell
> Naval Research Laboratory
> Monterey, CA
>
>

• References:
  • Plotting a recursion tree
    • From: metobillc <metobillc@gmail.com>