12

你可以在Mathematica中做类似 Python 的yield语句来创建生成器吗？有关概念，请参见此处。

更新 这是我的意思的一个例子，迭代所有排列，只使用O(n)空间：（算法在 Sedgewick 的算法书中）：

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

然后将其称为：

gen[Print,3]，打印长度为 3 的所有 6 个排列。

4

2 回答 2

5

正如我之前所说，使用Compile将给出更快的代码。使用来自fxtbook的算法，以下代码生成字典顺序的下一个分区：

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

以下代码假设我们运行版本 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
    ];

然后

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

Out[75]= True

这在性能上显然比原来的gen功能要好。

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

Out[83]= {26.067, Null}

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

Out[84]= {1.03, Null}

使用 Mathematica 的虚拟机并没有慢多少：

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

Out[85]= {1.154, Null}

当然，这与 C 代码实现相去甚远，但比纯顶级代码提供了显着的加速。

于 2011-04-18T16:03:30.610 回答
2

您可能的意思是这个问题更笼统，但是在您链接到的页面上给出的迭代排列的示例恰好内置在 Mathematica 中：

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

Print可以用任何功能替换。

于 2009-07-24T19:34:06.743 回答