3
$\begingroup$

Basically, it is a problem to convert a list to a tree.

Initially I have a list like this:

list={{0,0},{30,1},{30,2},{60,"a"},{60,"b"},{30,3}}

I need to do the following:

A. I have to compare the first sub-element of each of the elements of a list with the first sub-element of the element before.

B. According to the comparison, I have to implement the element into the first element of the list properly.

In particular:

  1. In the case mentioned above, I compare the 1st sub-element of the 1st element {0,0} and the 1st sub element of the 2nd element of the list {30,1}.

  2. 30 > 0 => I would like to insert a copy of the second element at the end of the first element.

{0,0} => {0,0,{30,1}}

This gives a list like this:

list={{0,0,{30,1}},{30,1},{30,2},{60,"a"},{60,"b"},{30,3}}
  1. After that, I go to the 3rd element of the list and compare its 1st sub-element with the 1st sub-element of the 2nd element.

  2. 30 = 30 => I would like to append a copy of the 2nd element at the end of the first element (after the element which was appended before).

=> {0,0,{30,1},{30,2}}

This gives a list like this:

list={{0,0,{30,1},{30,2}},{30,1},{30,2},{60,"a"},{60,"b"},{30,3}}
  1. Then again, I do the comparison of the 1st sub-elements of the 4th and the 3rd element. This is similar to the first step.

  2. 60 > 30 => I would like to insert a copy in the last sub-element of the 1st element.

=> {0,0,{30,1},{30,2,{60,"a"}}}

This gives the list like this:

list={{0,0,{30,1},{30,2,{60,"a"}}},{30,1},{30,2},{60,"a"},{60,"b"},{30,3}}
  1. Then the same comparison of the 1st sub-element of the 4th and the 5th element.

  2. 60 = 60 ->

=> {0,0,{30,1},{30,2,{60,"a"},{60,"b"}}}

list={{0,0,{30,1},{30,2,{60,"a"},{60,"b"}}},{30,1},{30,2},{60,"a"},{60,"b"},{30,3}}
  1. Comparing now the 1st sub-element of the 6th and the 5th element of the list.

  2. 30 < 60 ->

=> {0,0,{30,1},{30,2,{60,"a"},{60,"b"}},{30,3}}

list={{0,0,{30,1},{30,2,{60,"a"},{60,"b"}},{30,3}},{30,1},{30,2},{60,"a"},{60,"b"},{30,3}}
  • At the end I would like to drop all elements of the list except the 1st one and then I would like to display it as a tree:

{0,0}

->{30,1}

-->{30,2}

-->-->{60,"a"}

-->-->{60,"b"}

-->{30,3}

I hope, I was able to describe the issue now fully and correctly.

THX for your help!

$\endgroup$
2
  • $\begingroup$ I understand that you want to increase the last element of a list by 1. This can be done by e.g.: MapAt[# + 1 &, list, -1] $\endgroup$ Nov 6, 2022 at 13:17
  • $\begingroup$ Sorry, I guess my description of the issue was not that good. I try to precise the question a little bit below. $\endgroup$
    – JJJanezic
    Nov 6, 2022 at 14:17

1 Answer 1

1
$\begingroup$

I think this gives the specific result you want, but I think there may be some edge cases in the "real world" that you haven't accounted for in your description. So, this may need tweaking as you use it on more cases.

To make things easier, I'll introduce a wrapper MyTree and a function to add new nodes to a MyTree expression.

TreeAdd[trees : {___MyTree}, new : {newVal_, _}] :=
  With[
    {targetPosition = Position[trees, MyTree[{val_, _}, _] /; val < newVal, Infinity]},
    If[
      {} == targetPosition,
      Append[trees, MyTree[new, {}]],
      MapAt[TreeAdd[#, new] &, trees, Append[targetPosition[[-1]], 2]]]]

Given your definition for list, we will use Fold to build a tree.

listAsTree = Fold[TreeAdd, {}, list]

{MyTree[{0, 0}, {MyTree[{30, 1}, {}], MyTree[{30, 2}, {MyTree[{60, "a"}, {}], MyTree[{60, "b"}, {}]}], MyTree[{30, 3}, {}]}]}

Now for visualization. If you have a recent version of Mathematica, you might want to use Tree (and in fact you might want to use that from the start). It won't give you intended outline form, but it'll be an understandable visualization.

listAsTree /. MyTree -> Tree

Or you could use Grid, which will make the indentation easier:

TreeDisplay[tree_MyTree] := 
  Grid[
    {{tree[[1]], SpanFromLeft}, 
     {Spacer[30], Column[TreeDisplay /@ tree[[2]]]}}, 
    Alignment -> Left]

Now do

Column[TreeDisplay /@ listAsTree]

If you want a raw string, then something like this:

TreeString[indent_][tree_MyTree] := 
  StringJoin[{ConstantArray["  ", indent], ToString[tree[[1]]], "\n", TreeString[1 + indent] /@ tree[[2]]}]

and then

Column[TreeString[0] /@ listAsTree]

Update to address comment

If you need the partially flattened list, you can do this:

DeleteCases[listAsTree //. tree_MyTree :> FlattenAt[List @@ tree, 1], {}, Infinity]

{{0, 0, {{30, 1}, {30, 2, {{60, "a"}, {60, "b"}}}, {30, 3}}}}

$\endgroup$
3
  • $\begingroup$ Thank you very much, but it seems not working properly. Could you show me how to combine this so that I have list like {{0,0},{30,1},{30,2},{60,"a"},{60,"b"},{30,3}} and then call the function and get back {{0,0,{30,1},{30,2,{60,"a"},{60,"b"}},{30,3}}}? THX again! $\endgroup$
    – JJJanezic
    Nov 9, 2022 at 19:32
  • $\begingroup$ I can update, but you need to clarify first. In your comment about displaying it as a tree, you have the parent nodes as pairs. You indicated that this was what you wanted "at the end". If you destructure the pairs, you'll just have to recover them later. Is that really what you want? $\endgroup$
    – lericr
    Nov 9, 2022 at 19:37
  • $\begingroup$ I just went ahead and updated it, but I think I need to add the "use at your own risk" caveat. Without a clear idea of where this is headed and what the edge cases might be, I'm not really sure how robust any of this will be. $\endgroup$
    – lericr
    Nov 9, 2022 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.