Implementing Position

Question

As an assignment I need to re-implement Position. I've managed to do this except for one small thing, the resulting list is not in the current format. The following piece of code is what I have so far.

findPosition[lst_, x_] :=
  Module[{output = {}, index = 1},
    For[index = 1, index <= Length[lst], index++,
      If[lst[[index]] == x,
        AppendTo[output, {index}],
        False,
        If[MemberQ[lst[[index]], x],
          AppendTo[output, Map[{index, #} &, findPosition[lst[[index]], x]]];
          False
        ]; (* If *)
      ] (* If *)
    ]; (* For *)
    Return[output]
  ] (* Module *)

This gives the following output:

findPosition[{1, 2, {3, 2, 1}, {1, {4, 2, 1}, 2, {2, 6}}, {2, 6}}, 2]
{{2}, {{3, {2}}}, {{4, {{2, {2}}}}, {4, {3}}, {4, {{4, {1}}}}}, {{5, {1}}}}

While the original gives:

Position[{1, 2, {3, 2, 1}, {1, {4, 2, 1}, 2, {2, 6}}, {2, 6}}, 2]
{{2}, {3, 2}, {4, 2, 2}, {4, 3}, {4, 4, 1}, {5, 1}}

Am I doing something wrong or is there a way to make my result match the one from the original?

I've tried things using Flatten, but it's hard to control what is flattened and what is not. The closest I've come to is {{2}, {{3, 2}}, {{4, 2, 2}, {4, 3}, {4, 4, 1}}, {{5, 1}}} using

AppendTo[output, Map[Flatten[{index, #}] &, FindPosition[lst[[index]], x]]];

Answer 1

Your code will only work for nests that have two levels of nesting due to how you are mapping the index, but if this is fine, then the solution is to just Flatten the recursive call before you append it to output, and then Flatten the output of findPosition to get rid of some of the trailing braces. These changes give the following (NOTE: we also add and extra pair of {} to the single element case so the final Flatten works)

findPosition[lst_, x_] := Module[{output = {}, index = 1},
  For[index = 1, index <= Length[lst], index++,
   If[lst[[index]] == x,
     AppendTo[output, {{index}}],
     False,
   If[MemberQ[lst[[index]], x],
     AppendTo[output, 
     Map[Flatten[{index, #}] &, findPosition[lst[[index]], x]]];
     False];(*If*)
   ] (*If*)
  ];(*For*)
  Return[output]
] (*Module*)

with the final wrapper:

myPosition[lst_, x_] := Flatten[findPosition[lst, x], 1]

Now if we want do deal with arbirarly nested output we can do the following:

myPosition[lst_, x_] := First@Last@Reap[MapIndexed[If[MatchQ[#1, x], Sow[#2]] &, lst, Infinity];]

which works for all input, and should be much faster.