# Tag Info

## Hot answers tagged traversal

21

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]

17

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

17

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; {...

15

breadthFirst[expr_] := Flatten[Table[Level[expr, {j}], {j, 0, Depth[expr]}], 1] Running example: expr = {{1, {2, 3}}, {4, 5}}; breadthFirst[expr] (* Out[14]= {{{1, {2, 3}}, {4, 5}}, {1, {2, 3}}, {4, 5}, 1, {2, 3}, 4, 5, 2, 3} *)

14

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

13

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 = {...

12

expr = {{1, {2, 3}}, {4, 5}}; Do[Scan[Print, expr, {i}], {i, 0, Depth@expr}] {{1,{2,3}},{4,5}} {1,{2,3}} {4,5} 1 {2,3} 4 5 2 3

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] ...

8

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

8

As Kuba comments Level follows the standard expression traversal order: Level traverses expressions in depth-first order, so that the subexpressions in the final list are ordered lexicographically by their indices. This is actually a depth-first postorder traversal. It is the normal order in which expressions are evaluated in Mathematica: echo[x_] := (...

6

Based on my understanding of the question, you want to apply the rule to any expression, provided it wouldn't match any of its subexpressions. You can implement this traversal yourself quite easily with a recursive function, using FreeQ to check whether to go deeper or apply the rule: postOrderReplaceInnermost[expr_, rule_] := If[FreeQ[expr, rule[[1]], ...

6

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] :=...

6

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; ...

5

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 above....

5

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

4

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). ...

4

Daniel Lichtblau has confirmed that this is a problem with the integer linear programming code. Moreover, a bug report has been filed and the problem will be addressed in a future version.

3

Code head[h_[___]] := h; head[atom_] := Nothing; deconstruct[expr_] := With[ {temp = Flatten[Level[expr, {#}]& /@ Range[0, Depth[expr]], 1]}, {temp, head /@ temp} ]; Usage deconstruct[Sin[Log[Cos[a], Tan[Log[a, b]]]] // Inactivate] (* { {Inactive[Sin][Inactive[Log][Inactive[Cos][a], Inactive[Tan][Inactive[Log][a, b]]]], Inactive[Log][...

3

Second answer The OP's desired order: oporder = { {Inactive[Sin][Inactive[Log][Inactive[Cos][a], Inactive[Tan][Inactive[Log][a, b]]]], Inactive[Log][Inactive[Cos][a], Inactive[Tan][Inactive[Log][a, b]]], Inactive[Cos][a], Inactive[Tan][Inactive[Log][a, b]], a, Inactive[Log][a, b], a, b}, {Inactive[Sin], Inactive[Log], Inactive[Cos], Inactive[...

2

My first answer became a bit of a ramble so here is a second answer for a cleaner method. If speed is not a priority or if your expressions are not large you could use this: next[expr_, pos_] := Module[{f}, f[_, pos] := f[x_, _] := Return[x, MapIndexed]; MapIndexed[f, expr, {Length @ pos}] ] Examples: next[ListB, {1, 1, 2}] next[ListB, {1, 2,...

2

First, some observations on your code itself: There is a much more concise way to use Part (with Apply and SlotSequence): ListA[[##]] & @@ pos1 c More directly you can use Extract: Extract[ListA, pos1] c Your Flatten/Table code could done with Position: Position[ListA, _, {2}, Heads -> False] {{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, ...

2

With listA={{a,b,c},{d,e,f},{g,h,i}}; listB={{{a,b},{c}},{{d,e,f}},{{g},{h,i}}}; and the assumption that Flatten/@listB {{a, b, c}, {d, e, f}, {g, h, i}} always matches the dimensions of listA. One can create a lookup list for the positions posList=Flatten[ Table[{n,m},{n,1,Length@listA},{m,1,Length@listA[[1]]}] ,1] For ...

1

Your use of the head Inactive[] complicates this a bit, but generally, you'll want to do this: DeleteCases[DeleteCases[Reap[Scan[ Sow[#] &, (Sin[Log[Cos[a], Tan[Log[a, b]]]] // Inactivate), {0, Infinity}, Heads -> True]][[2, 1]], Inactive[x_]], Inactive] {Sin, Log, Cos, a, Inactive[Cos][a], Tan, Log, a, b, Inactive[Log][a, b], Inactive[...

1

Here is yet another attempt. If you want to take the next element many times, or take the second to next element, or the previous element, this may have an advantage. First, build an index between position and flattened position: index = Module[{cnt = 1}, Association @ Flatten @ MapIndexed[#2 -> (cnt++) &, ListB, {-1}]] <|{1, 1, 1} -> 1, {...

1

Here is another way: (Thread@{First@B, #[[1]], #[[2]]} & /@ Flatten[Rest@B, 1])~Flatten~1

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