Tag Info

Hot answers tagged

20

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]


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


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


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

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


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


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


7

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


7

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

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


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

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


3

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.


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

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

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