Registered: Not Yet
Location:
Posts: N/A

Fun APL/J Programming Problem

The following was posted within the last hour on comp.theory. Seems to = me a perfect candidate for
an APL or J solution. My J is rusty, so I'm = handing it over to you guys, and meanwhile heading for
the coffee shop = to scratch out the answer.

Cheers, Paul

----- Original Message -----=20 From: "Martijn Faassen" <m.faassen@vet.uu.nl> Newsgroups:
comp.theory Sent: Saturday, January 11, 2003 1:31 PM [UT] Subject: tree numbering schemes

[q1]> Hi there,[/q1]
[q1]>=20[/q1]
[q1]> In the course of some programming I ran into the following problem.[/q1]
[q1]>=20[/q1]
[q1]> Imagine I have a k-ary tree of a certain depth with no missing nodes=20 (I've heard that referred[/q1]
[q1]> to as a 'perfect k-ary tree', I think).[/q1]
[q1]>=20[/q1]
[q1]> I also assigned each node a number based on a level order traversal =[/q1]
scheme.
[q1]> Take for instance a binary tree of depth 3:[/q1]
[q1]>=20[/q1]
[q1]> 0[/q1]
[q1]> / \[/q1]
[q1]> 1 2[/q1]
[q1]> / \ / \[/q1]
[q1]> 3 4 5 6[/q1]
[q1]>=20[/q1]
[q1]> Is there a way to get from the level order numbers to the preorder =[/q1]
numbers
[q1]> without traversing the tree? i.e. I want to get to a tree numbered =[/q1]
like this:
[q1]>=20[/q1]
[q1]> 0 / \ 1 4=20 / \ / \ 2 3 5 6[/q1]
[q1]>=20[/q1]
[q1]> So, I'd like a function that given the level order number, the depth =[/q1]
of the
[q1]> tree and k returns the preorder number.[/q1]
[q1]>=20[/q1]
[q1]> I realize that in the case of non-perfect trees this is not possible =[/q1]
as=20
[q1]> there is missing information.. But it should be if you have a perfect =[/q1]
tree,
[q1]> and in constant time, right? But I can't figure it out, so I thought =[/q1]
I'd
[q1]> try asking some experts. Is there any literature I can look into? Anything online? I searched for[/q1]
[q1]> a while but only found a lot of =[/q1]
introductions
[q1]> to tree traversal algorithms but nothing about this.=20[/q1]
[q1]>=20[/q1]
[q1]> My real problem is a actually a bit more involved as I'm not dealing =[/q1]
with
[q1]> k-ary trees but trees which have a different amount of child nodes on each level (but the same for[/q1]
[q1]> each node on that level). Each level has the amount of child nodes associated with it. Still I[/q1]
[q1]> hope level_order->preorder is still possible in O(n) where n is the depth =[/q1]
of the
[q1]> tree.. Is that true? Any suggestions?[/q1]
[q1]>=20[/q1]
[q1]> Thanks,[/q1]
[q1]>=20[/q1]
[q1]> Martijn[/q1]

Report this post to a moderator | IP: Logged

Registered: Not Yet
Location:
Posts: N/A

Re: Fun APL/J Programming Problem

I'll generate the pre-order traversal sequence for a k-ary tree of depth m:

k=: 2 m=: 5 /: ; k&#.^:_1 each i. each k^i.m 1 3 7 15 16 8 17 18 4 9 19 20 10 21 22 2 5 11 23 24
12 25 26 6 13 27 28 14 29 30

In words: grade (/:) raze (;) k-ary-representation (k&#.^:_1) each integers (i.) each k to power
(k^) integers (i.) m. Salient parts of the solution:

k^i.m 1 2 4 8 16
i. each k^i.m

[q1]||0 1|0 1 2 3|0 1 2 3 4 5 6 7|0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15|[/q1]

k&#.^:_1 each i. each k^i.m +-+-+---+-----+-------+
[q1]||0|0 0|0 0 0|0 0 0 0|[/q1]
[q1]| |1|0 1|0 0 1|0 0 0 1|[/q1]
[q1]| | |1 0|0 1 0|0 0 1 0| 1 1|0 1 1|0 0 1 1|[/q1]
[q1]| | | |1 0 0|0 1 0 0| 1 0 1|0 1 0 1| 1 1 0|0 1 1 0| 1 1 1|0 1 1 1|[/q1]
[q1]| | | | |1 0 0 0| 1 0 0 1| 1 0 1 0| 1 0 1 1| 1 1 0 0| 1 1 0 1| 1 1 1 0| 1 1 1 1|[/q1]
+-+-+---+-----+-------+

Another example: k=: 3 m=: 4 /: ; k&#.^:_1 each i. each k^i.m 1 4 13 14 15 5 16 17 18 6 19 20 21 2 7
22 23 24 8 25 26 27 9 28 29 30 3 10 31 32 33 11 34 35 36 12 37 38 39

----- Original Message ----- From: "News Gateway" <owner-apl-l@sol.sun.csd.unb.ca> To:
<apl-l@listserv.unb.ca> Sent: Saturday, January 11, 2003 07:11 AM Subject: Fun APL/J
Programming Problem

X-From: "Paul Chapman" <paul@CHOPigblanCHOP.com>

The following was posted within the last hour on comp.theory. Seems to me a perfect candidate for an
APL or J solution. My J is rusty, so I'm handing it over to you guys, and meanwhile heading for the
coffee shop to scratch out the answer.

Cheers, Paul

----- Original Message ----- From: "Martijn Faassen" <m.faassen@vet.uu.nl> Newsgroups: comp.theory
Sent: Saturday, January 11, 2003 1:31 PM [UT] Subject: tree numbering schemes

[q1]> Hi there,[/q1]
[q1]>[/q1]
[q1]> In the course of some programming I ran into the following problem.[/q1]
[q1]>[/q1]
[q1]> Imagine I have a k-ary tree of a certain depth with no missing nodes (I've heard that referred to[/q1]
[q1]> as a 'perfect k-ary tree', I think).[/q1]
[q1]>[/q1]
[q1]> I also assigned each node a number based on a level order traversal =[/q1]
scheme.
[q1]> Take for instance a binary tree of depth 3:[/q1]
[q1]>[/q1]
[q1]> 0[/q1]
[q1]> / \[/q1]
[q1]> 1 2[/q1]
[q1]> / \ / \[/q1]
[q1]> 3 4 5 6[/q1]
[q1]>[/q1]
[q1]> Is there a way to get from the level order numbers to the preorder =[/q1]
numbers
[q1]> without traversing the tree? i.e. I want to get to a tree numbered =[/q1]
like this:
[q1]>[/q1]
[q1]> 0[/q1]
[q1]> / \[/q1]
[q1]> 1 4[/q1]
[q1]> / \ / \[/q1]
[q1]> 2 3 5 6[/q1]
[q1]>[/q1]
[q1]> So, I'd like a function that given the level order number, the depth of[/q1]
the
[q1]> tree and k returns the preorder number.[/q1]
[q1]>[/q1]
[q1]> I realize that in the case of non-perfect trees this is not possible as there is missing[/q1]
[q1]> information.. But it should be if you have a perfect[/q1]
tree,
[q1]> and in constant time, right? But I can't figure it out, so I thought I'd try asking some[/q1]
[q1]> experts. Is there any literature I can look into? Anything online? I searched for a while but[/q1]
[q1]> only found a lot of[/q1]
introductions
[q1]> to tree traversal algorithms but nothing about this.[/q1]
[q1]>[/q1]
[q1]> My real problem is a actually a bit more involved as I'm not dealing with k-ary trees but trees[/q1]
[q1]> which have a different amount of child nodes on each level (but the same for each node on that[/q1]
[q1]> level). Each level has the amount of child nodes associated with it. Still I hope[/q1]
[q1]> level_order->preorder is still possible in O(n) where n is the depth of[/q1]
the
[q1]> tree.. Is that true? Any suggestions?[/q1]
[q1]>[/q1]
[q1]> Thanks,[/q1]
[q1]>[/q1]
[q1]> Martijn[/q1]

Report this post to a moderator | IP: Logged

Registered: Not Yet
Location:
Posts: N/A

Re: Fun APL/J Programming Problem

Roger,

Thanks for that. Before I repost to comp.theory as an advertisment for = J, it'd be nice to complete
the script with the definition of 'each'.

Cheers, Paul

Report this post to a moderator | IP: Logged

Registered: Not Yet
Location:
Posts: N/A

Re: Fun APL/J Programming Problem

each=: &.>

This is automatically defined by the standard profile when you start up J.

Just as a matter of curiosity, how do you solve the problem in APL?

/: ; k&#.^:_1 each i. each k^i.m

i. each k^i.m would translate directly. k&#.^:_1 each would be more verbose. (k&#.^:_1 is not quite
(m/k){encode}x ) ; would also be more verbose (disclose ,[0] each/ does not quite do it). /:
(grade) would translate directly.

----- Original Message ----- From: "News Gateway" <owner-apl-l@sol.sun.csd.unb.ca> To:
<APL-L@LISTSERV.UNB.CA> Sent: Saturday, January 11, 2003 19:07 PM Subject: Re: Fun APL/J
Programming Problem

[q1]> X-From: "Paul Chapman" <paul@CHOPigblanCHOP.com>[/q1]
[q1]>[/q1]
[q1]> Roger,[/q1]
[q1]>[/q1]
[q1]> Thanks for that. Before I repost to comp.theory as an advertisment for = J, it'd be nice to[/q1]
[q1]> complete the script with the definition of 'each'.[/q1]
[q1]>[/q1]
[q1]> Cheers, Paul[/q1]

Report this post to a moderator | IP: Logged

Registered: Not Yet
Location:
Posts: N/A

Re: Fun APL/J Programming Problem

Happy New Year ...

Here's one APL approximate equivalent of Roger's code:-

As he says, k&#.^:_1 each needs a certain amount of circumlocution in APL, as in this function,
mkencode: {del} r{<-}mk mkencode x;m;k
[1] (m
k){<-}mk

[2]r{<-}(1{max}m{take}(2{log}{rho}x){rho}k){represent}x

{del}

We need m {take} of the encoding to force left-justification of the boolean matrix.

The rest is quite straightforward, albeit ugly in this transliteration format:

{gradeup}{transpose}{disclose},/({enclose}m
k)mkencode{each}{iota}{each}k*{iota}m 1 3 7 15 16 8 17 18 4 9 19 20 10 21 22 2 5 11 23 24 12 25 26 6
13 27 28 14 29 30

NB - you need origin zero, and this was run in Dyalog APL with #ml = 3

Mike 11 1 03

Roger Hui wrote:

[q1]>Just as a matter of curiosity, how do you solve the problem in APL?[/q1]
[q1]>[/q1]
[q1]> /: ; k&#.^:_1 each i. each k^i.m[/q1]
[q1]>[/q1]
[q1]>i. each k^i.m would translate directly. k&#.^:_1 each would be more verbose. (k&#.^:_1 is not quite[/q1]
[q1]> (m/k){encode}x ) ; would also be more verbose (disclose ,[0] each/ does not quite do it). /:[/q1]
[q1]> (grade) would translate directly.[/q1]

Report this post to a moderator | IP: Logged

Registered: Not Yet
Location:
Posts: N/A

Re: Fun APL/J Programming Problem

Here is a solution in J, different from the one Roger gave. I have posted it to the J forum already,
but I thought it's worth posting it to this newsgroup, too. My solution only generates short lists
(the depth of the tree in length), so it can handle much larger trees than that of Roger (provided
you use `extended integers'). Surely, list generation can be avoided altogether, but that would be
ugly to write in J.

NB. k = arity of the tree
NB. d = tree depth (starting from 0 for a single-node tree)
NB. n = node number in the level-order of nodes
NB. Last row computes the pre-order node number s=. k&#.\.d#1 r=. +/<:&n s c=. n-(<:r){|.s r+ (r{.s)
+/ .* (r#k)#:c

Example:

'k d n'=. 3 3 29 s=. k&#.\.d#1 r=. +/<:&n s c=. n-(<:r){|.s r+ (r{.s) +/ .* (r#k)#:c 25

Boyko B.

Report this post to a moderator | IP: Logged

Registered: Not Yet
Location:
Posts: N/A

Re: Fun APL/J Programming Problem

here's the k version of roger's solution:

<(,,0),/(+k _vs!:)'_k^!m

and a more general version of the problem:

you've got an arbitrary tree in l-r-breadth-first order, and you want to convert it to l-r
depth-first order.

e.g. you've got b:

0 -1 --3 --4 -2 --5 ---8 ---9 --6 --7

and you want d:

0 -1 --2 --3 -4 --5 ---6 ---7 --8 --9

represent b thus:

f: 0 0 1 1 2 2 2 5 5

b[0], the root, has itself as parent; the value of b[i] is the parent of i.

you want:

g: 0 1 1 0 4 5 5 4 4

the function to convert b's to d's is:

ga:{*|i\x i:<|:'x\'!#x}

db b 0 1 1 0 4 5 5 4 4

tracing through the function, with b for x:

!#b / iota count b
1 2 3 4 5 6 7 8 9

b\'!#b / tricky: get all paths to the root (,0 1 0 2 0 3 1 0 4 1 0 5 2 0 6 2 0 7 2 0 8 5 2
0 9 5 2 0)

|:'b\'!#b / reverse each
(,0 1 2 1 3 1 4 2 5 2 6 2 7 2 5 8 2 5 9)

<|:'b\'!#b / grade up -> the preordering of b 1 3 4 2 5 8 9 6 7

h:<|:'b\'!#b / i gets that

i\b i / tricky: start with b i, index i with the result until b i ( 0 1 1 0 2 5 5 2 2 0 1 1 0 3 5
5 3 3 0 1 1 0 4 5 5 4 4)

*|i\b i / d = the last of that 0 1 1 0 4 5 5 4 4

"Paul Chapman" <paul@CHOPigblanCHOP.com> wrote in message [url="news:8QVT9.12323$4k6.1046479@wards"]news:8QVT9.12323$4k6.1046479@wards[/url]... The
following was posted within the last hour on comp.theory. Seems to me a perfect candidate for an APL
or J solution. My J is rusty, so I'm handing it over to you guys, and meanwhile heading for the
coffee shop to scratch out the answer.

Cheers, Paul

----- Original Message ----- From: "Martijn Faassen" <m.faassen@vet.uu.nl> Newsgroups: comp.theory
Sent: Saturday, January 11, 2003 1:31 PM [UT] Subject: tree numbering schemes

[q1]> Hi there,[/q1]
[q1]>[/q1]
[q1]> In the course of some programming I ran into the following problem.[/q1]
[q1]>[/q1]
[q1]> Imagine I have a k-ary tree of a certain depth with no missing nodes (I've heard that referred to[/q1]
[q1]> as a 'perfect k-ary tree', I think).[/q1]
[q1]>[/q1]
[q1]> I also assigned each node a number based on a level order traversal scheme. Take for instance a[/q1]
[q1]> binary tree of depth 3:[/q1]
[q1]>[/q1]
[q1]> 0[/q1]
[q1]> / \[/q1]
[q1]> 1 2[/q1]
[q1]> / \ / \[/q1]
[q1]> 3 4 5 6[/q1]
[q1]>[/q1]
[q1]> Is there a way to get from the level order numbers to the preorder numbers without traversing the[/q1]
[q1]> tree? i.e. I want to get to a tree numbered like this:[/q1]
[q1]>[/q1]
[q1]> 0[/q1]
[q1]> / \[/q1]
[q1]> 1 4[/q1]
[q1]> / \ / \[/q1]
[q1]> 2 3 5 6[/q1]
[q1]>[/q1]
[q1]> So, I'd like a function that given the level order number, the depth of the tree and k returns the[/q1]
[q1]> preorder number.[/q1]
[q1]>[/q1]
[q1]> I realize that in the case of non-perfect trees this is not possible as there is missing[/q1]
[q1]> information.. But it should be if you have a perfect tree, and in constant time, right? But I[/q1]
[q1]> can't figure it out, so I thought I'd try asking some experts. Is there any literature I can look[/q1]
[q1]> into? Anything online? I searched for a while but only found a lot of introductions to tree[/q1]
[q1]> traversal algorithms but nothing about this.[/q1]
[q1]>[/q1]
[q1]> My real problem is a actually a bit more involved as I'm not dealing with k-ary trees but trees[/q1]
[q1]> which have a different amount of child nodes on each level (but the same for each node on that[/q1]
[q1]> level). Each level has the amount of child nodes associated with it. Still I hope[/q1]
[q1]> level_order->preorder is still possible in O(n) where n is the depth of the tree.. Is that true?[/q1]
[q1]> Any suggestions?[/q1]
[q1]>[/q1]
[q1]> Thanks,[/q1]
[q1]>[/q1]
[q1]> Martijn[/q1]

Report this post to a moderator | IP: Logged

Registered: Not Yet
Location:
Posts: N/A

Re: Fun APL/J Programming Problem

[q1]> the function to convert b's to d's is:[/q1]
[q1]>[/q1]
[q1]> db:{*|i\x i:<|:'x\'!#x}[/q1]
[q1]>[/q1]

it only occurred to me after posting this that going in the other direction - from depth-first to
breadth-first - requires a one character change:

bd:{*|i\x i:<#:'x\'!#x}

i.e., to get the breadth-first, sort the count of each path to the root.

factoring, we get:

j:{*|i\y i:<x'y\'!#y}
ja:t[|:] bd:t[#:]

b~bd db b 1

Report this post to a moderator | IP: Logged

Registered: Not Yet
Location:
Posts: N/A

Re: Fun APL/J Programming Problem

[q1]> |:'b\'!#b / reverse each[/q1]

Since K is more "functional" than APL, one can also write this as:
(|b\)'!#b / (reverse b scan) each iota shape b

If you do this, though, you miss the chance to factor the "reverse" out as Stevan shows in his
next message.
--
WildHeart'2k3

Report this post to a moderator | IP: Logged

Registered: Not Yet
Location:
Posts: N/A

Re: Fun APL/J Programming Problem

"Stefano Lanzavecchia" <wildstf@hotmail.com> wrote in message
[url="news:b0gh0l$oc162$1@ID-176142.news.dfncis.de"]news:b0gh0l$oc162$1@ID-176142.news.dfncis.de[/url]...
[q2]> > |:'b\'!#b / reverse each[/q2]
[q1]>[/q1]
[q1]> Since K is more "functional" than APL, one can also write this as:[/q1]
[q1]> (|b\)'!#b / (reverse b scan) each iota shape b[/q1]
[q1]>[/q1]
[q1]> If you do this, though, you miss the chance to factor the "reverse" out as Stevan shows in his[/q1]
[q1]> next message.[/q1]

nice one.

actually, you can still factor:

t:{*|i\y i:<(x y\)'!#y}
ta:t[|:] bd:t[#:]

[q1]> --[/q1]
[q1]> WildHeart'2k3[/q1]

Report this post to a moderator | IP: Logged

Registered: Not Yet
Location:
Posts: N/A

Re: Fun APL/J Programming Problem

sa wrote:
[q1]> here's the k version of roger's solution:[/q1]
[q1]>[/q1]
[q1]> <(,,0),/(+k _vs!:)'_k^!m[/q1]

Greg Heil proposed in the K listbox a solution which can be readily translated to APL without the
extra complication of the different definition of encode:

[q1]> ...eschewing the decoded intermediates...[/q1]
[q1]>[/q1]
[q1]> < ,/(|p)*'!:'p:_ k^!m[/q1]

In Dyalog APL, with #ML<-1 (to have enlist) and #IO<-0

gradeup enlist(reverse p) times iota each p<-k pow iota m

Notice that the second each (from the right) is not required in K either:

< ,/(|p)*!:'p:_ k^!m

--
WildHeart'2k3

Report this post to a moderator | IP: Logged