Replacement Rule for "flattening" list whilst adding attributes

I am struggling with replacement rules for what I am trying to and would appreciate any assistance.

In short, given an arbitrarily nested list (nl), I would like to create a list of lists ll, where each element (a list in the new list ll) contains some information about the structure about its corresponding nesting in nl.

For example:

ll = {1, 1, {2, 2, {3, {4}, 3}, 2}}
(* replacement rule *)
nl = {
(* el, index if flattened, level *)
{1, 1, 1},
{1, 2, 1},
{2, 3, 2},
{2, 4, 2},
{3, 5, 3},
{4, 6, 4},
{3, 7, 3},
{2, 8, 2}
}


If I try something like:

LeveledList[data___][request_] := Association[data][request]
LeveledList[list_List, level_Integer: 0] :=
LeveledList[
"data" ->
Replace[list, x_List :> LeveledList[x, level + 1], {1, Infinity}],
"level" -> level + 1]


Then ll becomes:

LeveledList[
"data" -> {1, 1,
LeveledList[
"data" -> {2, 2,
LeveledList[
"data" ->
LeveledList[
"data" -> {3,
LeveledList[
"data" ->
LeveledList[
"data" ->
LeveledList[
"data" -> LeveledList["data" -> {4}, "level" -> 4],
"level" -> 3], "level" -> 3], "level" -> 2], 3},
"level" -> 3], "level" -> 2], 2}, "level" -> 2]},
"level" -> 1]


Which keeps the nesting but adds level information.

This attempt gets the right data in this tuple structure, but it also converts keeps the nesting, which I need to drop...

ClearAll[TupledLeveledList];
TupledLeveledList[leveled_LeveledList] :=
Replace[
leveled,
ll_LeveledList :> Table[
{
ll["data"][[i]],
ll["level"],
i
}
, {i, Length[ll["data"]]}],
All
]


Although I can always convert back to normal via

ToNormal[l_LeveledList]:=Replace[l, ll_LeveledList:>ll["data"],All]

• are the roles of nl and ll switched in your second paragraph?
– kglr
Commented Jul 7, 2018 at 2:49
• @kglr not quite sure what you mean, but I just need to know some level specific data in a flattened form e.g. the non-list element, the flattened-index of said element, the level in which it was found and if it was the last element at that level (for a given sub-nesting). e.g. {1,{2,2},{2,2}} both of each last two would be the last of its given level (positions [[2,-1]] and [[3,-1]] respectively) Commented Jul 7, 2018 at 2:52
• I meant, given the example that follows it , shouldn't second paragraph the read "given a nested list (ll)..."? Or, Given your second paragraph, should the example read nl = {1,1, {2,2...}; ll={{1,1,1}...}?
– kglr
Commented Jul 7, 2018 at 2:59
• @kglr I can se how that can be confusing as both nl (nestedList) and ll (listOfLists) are actually nested lists. The difference being in that ll is structured (a tuple) and nl being unstructured (uneven nesting or arbitrary depth) Commented Jul 7, 2018 at 3:01
• Did any of the answers satisfied your need? There are things to do after your question is answered. It's a good idea to stay vigilant for some time, better approaches may come later improving over previous replies. Experienced users may point alternatives, caveats or limitations. New users should test answers before voting and wait 24 hours before accepting the best one. One weeks is enough wait. Participation is essential for the site, please do your part. Commented Jul 14, 2018 at 21:45

Update

To address the issue of indicating whether an element is the last at its depth:

extractListStructure[ll_, atomQ_: Not@*ListQ] :=

Block[{i = 1, prev = None},
Reap[
MapIndexed[
Function[
If[atomQ@#,
If[ListQ@prev,
prev[[4]] = False;
Sow@prev
];
prev = {#, i++, Length@#2, None},
If[ListQ@prev,
prev[[4]] = True;
Sow@prev;
prev = None
]
];
#
],
ll,
All
]
][[2, 1]]
];

extractListStructure@{1, 1, {2, 2, {3, {4}, 3}, 2}}

{
{1, 1, 1, False},
{1, 2, 1, False},
{2, 3, 2, False},
{2, 4, 2, False},
{3, 5, 3, False},
{4, 6, 4, True},
{3, 7, 3, True},
{2, 8, 2, True}
}


I also made this more flexible in format. It takes an atomQ which tells it whether to treat the thing as an element or something to loop over:

extractListStructure[
list[1, 1, {2, 2, {3, {4}, 3}, 2}],
MatchQ@Except[_list | _List]
]

{{1, 1, 1, False}, {1, 2, 1, False}, {2, 3, 2, False}, {2, 4, 2,
False}, {3, 5, 3, False}, {4, 6, 4, True}, {3, 7, 3, True}, {2, 8,
2, True}}


Not gonna lie, I didn't read your question carefully, so if I'm way off base tell me to take a hike.

But if you just want to get nl you can do it like so:

extractListStructure[ll_] :=
Module[{i = 1},
Reap[
MapIndexed[
If[! ListQ@#,
Sow[{#, i++, Length@#2}]
] &,
ll,
All
]
][[2, 1]]
];

extractListStructure@{1, 1, {2, 2, {3, {4}, 3}, 2}}

{
{1, 1, 1},
{1, 2, 1},
{2, 3, 2},
{2, 4, 2},
{3, 5, 3},
{4, 6, 4},
{3, 7, 3},
{2, 8, 2}
}

• going to look through it with some test examples, but looks like promising magic :) Commented Jul 7, 2018 at 1:45
• I am accepting as answer as you did answer the question asked, but I would like to ask a follow up if you have the time. I do not yet completely understand you code (reading docs now), so it is unclear to me how to modify it. How could I add a boolean flag in as a 4th item in the tuple as to if the element is the last element in its level. e.g. ... {4}, 3},2}... would be true the rest would be false Commented Jul 7, 2018 at 2:43
• @SumNeuron wait a bit to accept. Someone might come through with something better. There is no direct way to get that unfortunately as it is. Map[..., All] is processes element-wise so there are no "look-aheads". But I can rewrite this to only Sow after the element has been passed, effectively providing a look-ahead. I'll rewrite things a bit. Commented Jul 7, 2018 at 2:52
• that is the issue I am facing. I have several inelegant solutions for this with some recursive tables, but then I tried doing it symbolically - which was harder actually.. (at least for me). Just to clarify the last element in a level is specific to each instance of that level e.g. in {a, {b,c},{d,e}} both c and e are last elements in level 2, and there doesnt happen to be one for level 1. Commented Jul 7, 2018 at 2:55
• @SumNeuron see the edit, hopefully that does what you wat Commented Jul 7, 2018 at 3:01
MapThread[Append,
{MapIndexed[{#, #2[[1]]}&, Flatten @ ll],
Flatten @ MapIndexed[Length@#2&, ll, {-1}] }]


or

Join[MapIndexed[{#, #2[[1]]} &, Flatten@ll],
List /@ Flatten @ MapIndexed[Length@#2 &, ll, {-1}], 2]


{{1, 1, 1}, {1, 2, 1}, {2, 3, 2}, {2, 4, 2}, {3, 5, 3}, {4, 6, 4}, {3, 7, 3}, {2, 8, 2}}

Also

Block[{g}, Flatten[Module[{i = 1},
MapIndexed[g[#, i++, Length@#2] &, ll, {-1}]]] /. g -> List]


{{1, 1, 1}, {1, 2, 1}, {2, 3, 2}, {2, 4, 2}, {3, 5, 3}, {4, 6, 4}, {3, 7, 3}, {2, 8, 2}}

Update:

ClearAll[f]
f = Block[{g}, Module[{gb,
l1 = Flatten[Module[{i = 1}, MapIndexed[g[#, i++, Length@#2, #2] &, #, {-1}]]]},
gb = GatherBy[l1, Length[#[[-1]]] &];
gb[[All, -1, -1]] = True;
gb[[All, ;; -2, -1]] = False;
SortBy[Flatten @ gb, #[[2]] &]] /. g -> List] &;

f @ ll


{{1, 1, 1, False}, {1, 2, 1, True}, {2, 3, 2, False}, {2, 4, 2, False}, {3, 5, 3, False}, {4, 6, 4, True}, {3, 7, 3, True}, {2, 8, 2, True}}

• may I ask for your help again? I am struggling, in one pass, to - instead of whether or not an element is at its level instance - figure out at the lowest level an element is last at, e.g. {1,{{{2,3}},4},5}3 is last at level 4, but it's container is last at level 3 as wel... Commented Jul 9, 2018 at 0:04
• @SumNeuron, I will post an update if i can figure out a solution.
– kglr
Commented Jul 9, 2018 at 0:09
• you are too kind. I can do this with several passes of linear functions, but nothing that does it in one sweep Commented Jul 9, 2018 at 0:10
• @SumNeuron, what would be the desired output for the example {1,{{{2,3}},4},5}?
– kglr
Commented Jul 9, 2018 at 0:13
• if I use ... to make the closure more apparent (to myself) {1, {..., 4}, 5} the elements inside the list {..., 4} are at level 2, but the list itself is level 1. So I think I internally skipped a beat and made this lvl-1 adjustment (which I do for my application). e.g. if I changed it to {1,{{{2,3}, 6},4},5}, the value for 3 would not change, as while 3 is at level 4, its list container is at level 3, 6 would be at level 2 and 4 remains at level 1. ugh this is a headache :D Commented Jul 9, 2018 at 0:40