Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Yield in Mathematica

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.

like image 556
nes1983 Avatar asked Jul 22 '09 14:07

nes1983


1 Answers

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.

like image 188
Sasha Avatar answered Sep 20 '22 17:09

Sasha