4
$\begingroup$

I'm still new to this language and have tried a number of ways with no success. I have a list of keys with values. These values are used to identify the parent of the current item. The list is ordered, so I just need to look before the current item to find its parent. Here's an example:

{{"A1", 1}, {"B1", 2}, {"B2", 2}, {"B3", 2}, {"C1", 3}, {"B4", 2}, {"C2", 3}, {"C3", 3}, {"A2", 1}, {"B5", 2}, {"C1", 3}, {"C2", 3}, {"C3", 3}, {"B6", 2}, {"B7", 2}}

Looking at this list, we see that A1 is a parent, and the B's after it are it's children (because their value is 2). C1 would be a child of B3. B4 would be a child of A1. This is basically a tree. The result would be like this (parent can be blank or just the value of the parent). Please ignore the keys, they can be anything, we want to use the values only. Notice how the parent is reset to "A2" when you get to "B5", because the value of "A2" was 1:

{{"A1", ""}, {"B1", "A1"}, {"B2", "A1"}, {"B3", "A1"}, {"C1", "B3"}, {"B4", "A1"}, {"C2", "B4"}, {"C3", "B4"}, {"A2", ""}, {"B5", "A2"}, {"C1", "B5"}, {"C2", "B5"}, {"C3", "B5"}, {"B6", "A2"}, {"B7", "A2"}}
$\endgroup$
  • 1
    $\begingroup$ I don't get the rules. Why is "C1" a child of "B3"? And what is the question btw.? $\endgroup$ – Henrik Schumacher Jul 4 at 20:33
  • $\begingroup$ Moreover, Mathematica's way of representing a tree is Graph[ {"A1" -> "B1", "A1" -> "B2", "A1" -> "B3", "B3" -> "C1", "A1" -> "B4"}, VertexLabels -> "Name" ]. So a parent points to its children. You can also reverse the directions, of course. $\endgroup$ – Henrik Schumacher Jul 4 at 20:35
4
$\begingroup$

Try this

t={{"A1",1},{"B1",2},{"B2",2},{"B3",2},{"C1",3},{"B4",2},{"C2",3},{"C3",3},
   {"A2",1},{"B5",2},{"C1",3}, {"C2",3},{"C3",3},{"B6",2},{"B7",2}};
Table[{t[[i,1]],v=Cases[Take[t,i-1],{_,t[[i,2]]-1}];If[Length[v]>0,v[[-1,1]],""]},
  {i,1,Length[t]}]

which returns this

{{"A1", ""}, {"B1", "A1"}, {"B2", "A1"}, {"B3", "A1"}, {"C1", "B3"}, {"B4", "A1"},
 {"C2", "B4"}, {"C3", "B4"}, {"A2", ""}, {"B5", "A2"}, {"C1", "B5"}, {"C2", "B5"},
 {"C3", "B5"}, {"B6", "A2"}, {"B7", "A2"}}

That builds a table with each entry containing the name of the individual and the name of the most recent individual in the list who has an index one less than the current individual. It substitutes a blank name if no such recent individual exists.

Please test this exhaustively to make certain that every detail is correct for every combination of parentage.

Since you are new at this perhaps this alternate code might be easier to start with.

people={{"A1",1},{"B1",2},{"B2",2},{"B3",2},{"C1",3},{"B4",2},{"C2",3},{"C3",3},
        {"A2",1},{"B5",2},{"C1",3}, {"C2",3},{"C3",3},{"B6",2},{"B7",2}};
Table[
  {person,level}=people[[i]];
  predecessors=Take[people,i-1];
  onelevelup=Cases[predecessors,{_,level-1}];
  parent=If[Length[onelevelup]==0,"",onelevelup[[-1,1]]];
  {person,parent},
  {i,1,Length[people]}]

You can look up each of those functions and often even look up "odd" punctuation in the help system. Click on the orange "details and options" there to learn more about how each thing works.

$\endgroup$
  • $\begingroup$ That seems to be working, thank you so much. I'm going to go through your solution to make sure I understand it. $\endgroup$ – Sam B Jul 4 at 20:52
2
$\begingroup$

Given:

$data = {{"A1", 1}, {"B1", 2}, {"B2", 2}, {"B3", 2}, {"C1", 3}, {"B4", 2}, {"C2", 3}, {"C3", 3}, {"A2", 1}, {"B5", 2}, {"C1", 3}, {"C2", 3}, {"C3", 3}, {"B6", 2}, {"B7", 2}};

$expected = {{"A1", ""}, {"B1", "A1"}, {"B2", "A1"}, {"B3", "A1"}, {"C1", "B3"}, {"B4", "A1"}, {"C2", "B4"}, {"C3", "B4"}, {"A2", ""}, {"B5", "A2"}, {"C1", "B5"}, {"C2", "B5"}, {"C3", "B5"}, {"B6", "A2"}, {"B7", "A2"}};

... then we can produce the expected result in a single pass through the list:

$result = Module[{parent}
, parent[1] = ""
; Replace[{id_, level_} :> (parent[level+1] = id; {id, parent[level]})] /@ $data
];

$result === $expected
(* True *)

This uses a helper function, parent which will be able to return parent identifier for each level of the tree. The function is seeded with the parent of level 1, namely "". Then, the list is scanned from left-to-right using /@ (also known as Map) to transform entry of the data list using Replace. Each transformation does two things:

  • it updates the parent function so that the current node is recorded as the parent for the next level down, and then
  • it generates the desired output for each node: a list of the node's ID and its parent's ID.

We can plot the resulting tree to verify that we have properly handled the cases of C1, C2 and C3 which each appear under multiple parents:

TreePlot[Curry[Rule] @@@ $result, Top, "", VertexLabels -> Automatic]

tree plot

$\endgroup$
2
$\begingroup$

An alternative approach using SequenceCases:

lst = {{"A1", 1}, {"B1", 2}, {"B2", 2}, {"B3", 2}, {"C1", 3}, 
 {"B4", 2}, {"C2", 3}, {"C3", 3}, {"A2", 1}, {"B5", 2}, {"C1", 3},
 {"C2", 3}, {"C3", 3}, {"B6", 2}, {"B7", 2}};

rule = {{a_, b_}, {_, Except[b_]} ..., {c_, d_}} /; b == d - 1 :> {c, a};
result = SequenceCases[Prepend[lst, {"", 0}], rule, Overlaps -> All]

{{"A2", ""}, {"A1", ""}, {"B4", "A1"}, {"B3", "A1"}, {"B2", "A1"}, {"B1", "A1"},
{"C1", "B3"}, {"C3", "B4"}, {"C2", "B4"}, {"B7", "A2"}, {"B6", "A2"},
{"B5", "A2"}, {"C3", "B5"}, {"C2", "B5"}, {"C1", "B5"}}

Graph[Union @ Flatten[result], DirectedEdge @@@ (Reverse /@ result), 
 GraphLayout -> "LayeredEmbedding", 
 VertexSize -> Large, VertexLabels -> Placed["Name", Center]]

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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