It is not easy to find realistic examples small enough for demonstration, but
consider a child dressing for playing outdoors in the cold. He must put on a
flying suit, boots, hat, and mittens. The order is not completely free, because
he cannot take on the flying suit once he has put on the boots, and he cannot
dress with mittens on. The activities are described in a diagram where flying
suit is in series with boots, and hat is in parallel with flying suit+boots.
The diagram can be expressed by a formula like this
((flying suit+boots)||hat)+mittens
or by using ordinal fraction like this.
111 flying suit
112 boots
12 hat
2 mittens.
Every other digit position represents series and parallel.
There are two boots and two mittens, so the description can be more detailed.
111 flying suit
1121 left boot
1122 right boot
12 hat
21 left mitten
22 right mitten
Series means that order matters, and parallel means that order does not matter.
Draw the diagram on the back of an envelope.
Thank you.
Bo.
Den 17:18 fredag den 22. december 2017 skrev "Dabrowski, Andrew John"
<[email protected]>:
Got it, thank you.
On Dec 22, 2017 9:54 AM, Raul Miller <[email protected]> wrote:
Sure:
'data indices'=. 'abcdeq';__ 0 1 1 1 0
We see that b and q have a as their parent:
data {~ indices {~ data i.'bq'
aa
And, we see that c d and e have b as their parent:
data {~ indices {~ data i.'cde'
bbb
And when we look at the diagram, we see the same thing:
c
/
b - d
/ \
a e
\
q
So, for example:
insert_under=:dyad define
'old_data old_indices'=. y
'new_data new_parents'=. x
data=.old_data,~.new_data -. old_data
data;old_indices,old_data i. ($new_data)$new_parents
)
Example use:
('jkl';'d') insert_under 'abcdeq';__ 0 1 1 1 0
That said, beware that like most tree implementations, this is a
solution searching for a problem. (Which is itself a problem, since
usually we need solutions to real life problems - and this usually
takes us way outside our comfort level. Which tends to snowball until
either someone fixes it or ... not ...).
Thanks,
--
Raul
newparents=.
Thanks,
--
Raul
On Fri, Dec 22, 2017 at 9:18 AM, Dabrowski, Andrew John
<[email protected]> wrote:
>
>
> On Dec 22, 2017 12:50 AM, Raul Miller <[email protected]> wrote:
> I'm not sure about ordinal fractions, but one way of representing that
> tree in J is:
>
> 'abcdeq';__ 0 1 1 1 0
>
> Here, we have a pair of lists, the first is data, the second is structure.
>
> The structural values are the index of the parent
>
> Could you explain this? I might have thought it would be
>
> 'abqcde';_ 0 1 0 1 2
>
>
>
> node. This approach
> allows for relatively simple insertion. (Delete makes things more
> complex but you can get rid of indexes and perhaps even replace the
> corresponding data element with fill. This requires a later garbage
> collect operation.)
>
> Sometimes it might make things easier to have the root node be the
> parent of itself.
>
> Like any J implementation, scalar traversal will tend to be
> inefficient, but if you can operate on the structure as a whole you
> can get good performance. (This also suggests that inserts and deletes
> would ideally be done en-masse rather than bit by bit.)
>
> Now... whether a tree structure is worth implementing is another
> issue. For example, OS directory structures can serve as tree
> structures, and sometimes are a good choice.
>
> Then again ... trees are often used primarily to represent a flat
> list "efficiently" for a small-step-at-a-time algorithm, and that an
> approach based on flat lists might be more efficient if you can group
> up the inserts and deletes in a good way...
>
> Of course, often people use trees because it's fun to re-invent the wheel.
>
> But I guess what I'm saying is that trees can sometimes be a "code smell".
>
> Thanks,
>
> --
> Raul
>
> On Thu, Dec 21, 2017 at 10:21 PM, David Lambert <[email protected]> wrote:
>> I'd use an index vector to store the ordinal fraction as I understand them.
>> Check my comprehension please. Do the ordinal fractions and tree agree?
>>
>>
>> c
>> /
>> b - d
>> / \
>> a e
>> \
>> q
>>
>>
>> 0 0 0 a
>> 0 1 0 b
>> 0 2 0 q
>> 0 1 1 c
>> 0 1 1 d
>> 0 1 2 e
>>
>>
>> Boxes take a long time in j because, among other things, each open box must
>> be type and shape and rank checked.
>>
>> Under ordinal fraction addressing scheme, is there a way to know that data
>> is stored internally as a regular array? Knowing the stride between items
>> is key to fast execution.
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
