Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
1  
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? –  Sjoerd C. de Vries May 20 '12 at 9:51
    
It is a given that all left branches are numbers (and even more specifically, integers). Thanks. –  Andrew May 20 '12 at 15:40

3 Answers 3

up vote 21 down vote accepted

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]
share|improve this answer
1  
I don't think I can beat this! –  rm -rf May 18 '12 at 21:58
1  
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 –  rm -rf May 18 '12 at 22:02
2  
@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. –  rm -rf May 19 '12 at 1:22
1  
@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. –  Leonid Shifrin May 26 '12 at 16:19
1  
@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}}}}. –  Michael Wijaya Aug 19 '12 at 2:14

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}}
share|improve this answer
    
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}}}} –  acl May 26 '12 at 14:39

Here is another way:

(Thread@{First@B, #[[1]], #[[2]]} & /@ Flatten[Rest@B, 1])~Flatten~1
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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