14
$\begingroup$

I have a list:

B={423, {{53, {39, 65, 423}}, {66, {67, 81, 423}}, {424, {25, 40, 423}}}};

This list can be visualized as a tree using TreeForm[B]:

TreeForm[B]

and I would like to find all possible traversals of this tree:

{{423,53,39},{423,53,65},{423,53,423},{423,66,67},{423,66,81},
 {423,66,423},{423,424,25},{423,424,40},{423,424,423}}

It seems that Subset might be usable, but when I tried Subset[B,{3}], it gave me the null set. Another possible problem with Subset is that it perhaps does not respect the leveling of the tree. I looked at the Combinatorica package, but I don't see a way to traverse the tree -- in the direction from top to bottom -- in all possible ways.

$\endgroup$
  • 1
    $\begingroup$ Are you looking for solutions for this specific tree B or for general trees? B has the property that all left branches are numbers. Is that a given? $\endgroup$ – Sjoerd C. de Vries May 20 '12 at 9:51
  • $\begingroup$ It is a given that all left branches are numbers (and even more specifically, integers). Thanks. $\endgroup$ – Andrew May 20 '12 at 15:40
22
$\begingroup$

Here is one way:

ClearAll[f];
f[tree_List] := Flatten[f[{}, tree], 1];
f[accum_List, {x_, y_List}] := f[{accum, x}, #] & /@ y;
f[x_, y_] := Flatten[{x, y}];

The usage is

f[B]
$\endgroup$
  • 1
    $\begingroup$ I don't think I can beat this! $\endgroup$ – rm -rf May 18 '12 at 21:58
  • 1
    $\begingroup$ Uhh whoa! That's my line, when you say something like my comment! Not the other way round :) I've just thrown in the towel at Step 0 :P $\endgroup$ – rm -rf May 18 '12 at 22:02
  • 2
    $\begingroup$ @Andrew You can replace the first definition for f with f[tree_List] := Flatten[f[{}, tree], {1}];. The additional change as a result of this is that the final output will have all the paths from each "major branch" (or what ever the right term is) grouped together. I actually like it this way and you can flatten this out appropriately in a post-processing step. Run the new definition on B to see what I mean. $\endgroup$ – rm -rf May 19 '12 at 1:22
  • 1
    $\begingroup$ @acl Thanks for the upvote and kind words. The thing is, I was prepared for this question, having done similar things in the past. What may look clever from the outset is often just a result of some practice and preparation, you just have to think in a certain direction. Once you apply some new (to you) technique a few times, it grows on you and leads your thoughts, and then it is not particularly hard. I think this applies to anything (I do know from experience that it also applies to physics and math). You just need to have a free mind and time to experiment on your own, that's all. $\endgroup$ – Leonid Shifrin May 26 '12 at 16:19
  • 1
    $\begingroup$ @Andrew We can also replace the first definition of f by f[tree_List] := List@@@Flatten@Apply[lst, f[{}, tree], {-2}];. Now f will work for {423,{53,66,424}} as well as {423, {{53, {39, {66, {67, 81, 423}}, 423}}, {66, {67, 81, 423}}, {424, {25, 40, 423}}}}. $\endgroup$ – Michael Wijaya Aug 19 '12 at 2:14
5
$\begingroup$

Here is a transformation that will work as well:

Flatten[B //. {
   {x__?NumericQ, {y__?NumericQ}} :> ({x, #} & /@ {y}),
   {x__?NumericQ, {y__List}} :> (Join[{x}, #] & /@ {y})
   }, 1]

yields

{{423, 53, 39}, {423, 53, 65}, {423, 53, 423}, {423, 66, 67}, {423, 
  66, 81}, {423, 66, 423}, {423, 424, 25}, {423, 424, 40}, {423, 424, 
  423}}
$\endgroup$
  • $\begingroup$ nice, +1. however this doesn't seem to work generically ; try with {423, {{53, {39, 65, 423}}, {66, {67, 81, 423}}, {424, {25, 40, {4, 3, 4, 2}, 423}}}} $\endgroup$ – acl May 26 '12 at 14:39
2
$\begingroup$

Here is another way:

(Thread@{First@B, #[[1]], #[[2]]} & /@ Flatten[Rest@B, 1])~Flatten~1
$\endgroup$
  • $\begingroup$ Seems to break with trees with variable-depth branches: eg try B2 = {423, {{53, {39, 65, 423}}, {66, {67, 81, 423}}, {424, {25, {40, 41}}}}}; $\endgroup$ – alancalvitti Feb 26 '18 at 18:14

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.