Yield in Mathematica

Question

Can you do something like Python's yield statement in Mathematica, in order to create generators? See e.g. here for the concept.

Update Here's an example of what I mean, to iterate over all permutations, using only O(n) space: (algorithm as in Sedgewick's Algorithms book):

gen[f_, n_] := Module[{id = -1, val = Table[Null, {n}], visit},
  visit[k_] := Module[{t},
    id++; If[k != 0, val[[k]] = id];
    If[id == n, f[val]];
    Do[If[val[[t]] == Null, visit[t]], {t, 1, n}];
    id--; val[[k]] = Null;];
  visit[0];
  ]

Then call it it like:

gen[Print,3], printing all 6 permutations of length 3.

Answer 1

As I have previously stated, using Compile will given faster code. Using an algorithm from fxtbook, the following code generates a next partition in lexicographic ordering:

PermutationIterator[f_, n_Integer?Positive, nextFunc_] := 
 Module[{this = Range[n]},
  While[this =!= {-1}, f[this]; this = nextFunc[n, this]];]

The following code assumes we run version 8:

ClearAll[cfNextPartition];
cfNextPartition[target : "MVM" | "C"] := 
  cfNextPartition[target] = 
   Compile[{{n, _Integer}, {this, _Integer, 1}},
    Module[{i = n, j = n, ni, next = this, r, s},
     While[Part[next, --i] > Part[next, i + 1], 
      If[i == 1, i = 0; Break[]]];
     If[i == 0, {-1}, ni = Part[next, i]; 
      While[ni > Part[next, j], --j];
      next[[i]] = Part[next, j]; next[[j]] = ni;
      r = n; s = i + 1;
      While[r > s, ni = Part[next, r]; next[[r]] = Part[next, s]; 
       next[[s]] = ni; --r; ++s];
      next
      ]], RuntimeOptions -> "Speed", CompilationTarget -> target
    ];

Then

In[75]:= Reap[PermutationIterator[Sow, 4, cfNextPartition["C"]]][[2, 
   1]] === Permutations[Range[4]]

Out[75]= True

This is clearly better in performance than the original gen function.

In[83]:= gen[dummy, 9] // Timing

Out[83]= {26.067, Null}

In[84]:= PermutationIterator[dummy, 9, cfNextPartition["C"]] // Timing

Out[84]= {1.03, Null}

Using Mathematica's virtual machine is not much slower:

In[85]:= PermutationIterator[dummy, 9, 
  cfNextPartition["MVM"]] // Timing

Out[85]= {1.154, Null}

Of course this is nowhere near C code implementation, yet provides a substantial speed-up over pure top-level code.