Подтвердить что ты не робот

Выход в Mathematica

Можете ли вы сделать что-то вроде выражения Python yield в Mathematica для создания генераторов? Смотрите, например, здесь для концепции.

Обновить Вот пример того, что я имею в виду, чтобы перебрать все перестановки, используя только пространство O(n): (алгоритм как в книге Sedgewick Algorithms):

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], печать всех 6 перестановок длины 3.

4b9b3361

ОТВЕТЫ

Ответ 1

Как я уже говорил, использование 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, но обеспечивает существенное ускорение по сравнению с чистым кодом верхнего уровня.

Ответ 2

Вероятно, вы хотите, чтобы вопрос был более общим, но пример итерации над перестановками, как указано на странице, на которую вы ссылаетесь, находится в Mathematica:

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

Print его можно заменить любой функцией.