Tag Info

Hot answers tagged

15

Here is a simple implementation of a breadth first traversal. It simply maps the function onto each element on the current level and then collects all non-atomic entries into the next level, rinse and repeat. breadthFirstApply[{}, call_] := Null breadthFirstApply[list_, call_] := (call /@ list;breadthFirstApply[Level[list,{2}], call]) Output with your ...


13

Here is an expressly iterative solution: bf[f_, x_] := ((f~Scan~#; #~Level~{2})& ~FixedPoint~ {x};) (* In[2]:= bf[Print, {{1, {2, 3}}, {4, 5}}] {{1,{2,3}},{4,5}} {1,{2,3}} {4,5} 1 {2,3} 4 5 2 3 *) Incorporating Rojo's advice to Hold expressions gathered by Level: bf[f_, x_] := ( Level[f~Scan~#; #, {2}, Hold] & ~FixedPoint~ {x} ;)


11

I am aware of two general methods. ReplaceAll The only general purpose function I am aware of that visits depth-first preorder is ReplaceAll. One can "scan" a given function such as Print as a side-effect by using either PatternTest or Condition, both of which only match if the return is explicitly True. {{1, {2, 3}}, {4, 5}} /. _?Print -> Null; ...


10

The {0} represents the head of the expression. For example, l[[0]] (* ==> List *) About {}, the docs say A part specification {} returned by Position represents the whole of expr. You get these results because Position searches the expression at all levels. To get what you were looking for, use Position[l, Except[0], {1}, Heads -> False] ...


9

Here is a version that uses an explicit stack to avoid recursion. depthFirstPreorder[expr_] := Module[ {stack = {expr, {}}, el = expr}, Reap[ While[stack =!= {}, {el, stack} = stack; Sow[el]; If[Not[AtomQ[el]], Do[stack = {el[[j]], stack}, {j, Length[el], 1, -1}]]; ]; ][[2, 1]] ] The customary example: expr = ...


6

I meant my comment above as a joke, but here's the implementation anyway. Some ugly recursive code to convert the expression to a Graph: ClearAll[treeBuild] treeBuild[expr_[ops___]] := treeBuild[expr, #] & /@ {ops} treeBuild[name_, expr_[ops___]] := Module[{node = Unique[expr]}, {name \[DirectedEdge] node,treeBuild[node, #] & /@ {ops}}] ...


5

Don't know where this should fit. Playing around, this could be a more general approach to the traversal problem. It's probably not best for those traversals that can be done in other ways. Specifically, it has to create the list of indices all at once so it's not memory efficient as Scan Module[{tag}, generalScan[fun_, expr_, sortingFun_: RandomSample] ...


5

TreeForm lays the expression tree out in a depth-first preorder traversal fashion. So observing that using VertexLabeling -> Tooltip gives you the expression at that level, we can redefine Tooltip using the Villegas–Gayley trick to print out the expressions as TreeForm lays out the tree. Replace Print with any desired function. Unprotect@Tooltip; ...


4

My answer to the breadth first scan question (convert your expression to a Graph and do a BreadthFirstScan) can also be used for the depth first scan (if you have MMA v8). You only need to replace BreadthFirstScan by DepthFirstScan. The latter is apparently (and luckily in this case) of the pre-order type. For the code I refer to the answer referenced ...


4

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}}


3

A package-ready breadth-first position search, returning positions of a pattern in an expression. It allows top-down and bottom-up breadth-first traversals by setting level specification. It is not exactly the one Mr.Wizard was looking for, as it checks absolute levels rigorously (i.e. all level 4 subparts are checked before any level 3 subpart is visited). ...



Only top voted, non community-wiki answers of a minimum length are eligible