13

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.

Improve this question
4
  • FWIW, Python's way of doing iterators / generators is rather unusual. As long as you have some sort of abstraction over state (closures, classes), you can implement them in any langauge. Commented Jul 22, 2009 at 14:37
  • Ah, nice. Maybe add that as an answer to your own question (it's considered quite kosher to do that). Or is there still a question unanswered here? Commented Jul 30, 2009 at 17:45
  • Well, you need to explicitly pass your functions around, while the Python yield thing kind of figures it out for you, and makes it fit into the framework. So, it isn't quite perfect. But good enough, indeed, I use it now. Commented Jul 30, 2009 at 19:54
  • The code quoted from the book is fine, but being written in top-level Mathematica, it is not the most efficient, will run slow for larger n. You might want to write nextPermutation in Compile, and then loop through permutations. Added benefit, you can compile it into C in v8 to improve performance about 10 times. Commented Mar 3, 2011 at 15:50

2 Answers 2

Reset to default
6

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

You can get C speed by using the trick I was exposing in this post: stackoverflow.com/questions/5246330/…. If you create a generator for a compiled function PermutationIterator, like so: PermutationIteratorGen[f_, nextFunc_] := Compile[{{n, _Integer}}, Module[{this = Range[n]}, While[this =!= {-1}, f[this]; this = nextFunc[n, this]];], RuntimeOptions -> "Speed", CompilationTarget -> "C", CompilationOptions -> {"InlineCompiledFunctions" -> True, "InlineExternalDefinitions" -> True}], contd..
Continuing.. Then, assuming that your dummy function can be Compiled, you get another order of magnitude speedup: fn = PermutationIteratorGen[# &, cfNextPartition["C"]]; fn[9] // Timing. The trick above effectively allows the variables of the enclosing Compiled function to live in the compiled code and be modified by the caller compiled function, because at the end we do inlining and get just a single large Compiled function, but for us it looks more modular. But using Sow or other uncompilable function will greatly degrade the performance, thus almost no difference between C and MVM.
@Leonid Yes this a good point, and the iterator also can be custom written to perform some predetermined operations, thus forgoing passing the function altogether. What I meant by not C-speed is that it is far from 130 millions permutations generated per second quote made in fxtbook. fn[11] takes 9.86 seconds on my machine amounting to 4 million permutations per second. A look at CompilePrint[fn] is instructive and will indicate why that happened.
@Sasha Thanks, I should have looked at CompilePrint indeed. I do that in other cases but here I somehow believed that there would be no calls to the main evaluator and did not check, The same is true for the code I referred to, as you commented there.
@Sasha Strange: I actually looked at CompilePrint[fn], and did not find there the calls to the main evaluator. There were, however, multiple calls to CopyTensor, but I assume that CopyTensor is some Wolfram Runtime Library function linked to the generated C code, so it should be fast enough. So, I still don't see what could account for such dramatic speed difference between the timings you quote from the book and the ones that fn evaluation gives. I could only guess that, since there is a lot of small array memory allocatiion-deallocation involved, this could be the major factor.
|
2

You probably mean the question to be more general but the example of iterating over permutations as given on the page you link to happens to be built in to Mathematica:

Scan[Print, Permutations[{1, 2, 3}]]

The Print there can be replaced with any function.

Improve this answer

1 Comment

Well, what I mean by a generator is this more like the following, which works in O(n) memory, where you need O(n!). 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]; ] You run it like this: gen[Print,3]

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.