162
правки
Изменения
Нет описания правки
</center>
Монотонный код Грея может быть эффективно сгенерирован по этому алгоритму за время <tex>O(n)</tex>. Легче всего написать этот алгоритм используя сопрограммугенератор.
=== Псевдокод ===
Перед тем как писать псевдокод необходимо объяснить что такое <code>'''yield'''</code> и что понимать под выражениями типа <code>(0,)</code> или <code>(1,)</code>.
<code>'''yield'''</code> - аналог <code>'''return'''</code> только для функций-генераторов. То есть генераторы это тоже итерируемые объекты, но прочитать их можно лишь один раз. Это связано с тем, что они не хранят значения в памяти, а генерируют их на лету.
С конструкциями типа <code>(0,)</code> или <code>(1,)</code> все проще. Используя ее совместно с <code>'''yield'''</code> мы можем в изменять наш генерируемый объект. Например, <code>'''yield''' (0,)</code> допишет к генерируемому объекту (в нашем случае кортежу (англ. ''tuple'')) <tex>0</tex> в начало.
{| border="0"
|align="left" colspan="4"|
*Вспомогательная функция для генерации перестановки, циклически сдвигает битовый вектор направо <tex>n</tex> раз.
*Принимает и возвращает котреж. Кортеж аналог списка, но в кортеже нельзя менять элементы, можно только добавлять.
<code>
rotateRight(x, n):<font color=green> // Вспомогательная функция для генерации перестановки, циклически сдвигает битовый вектор направо <tex>n</tex> раз. Принимает и возвращает котреж (англ. ''tuple''). Кортеж аналог списка, но в кортеже нельзя менять элементы, можно только добавлять.</font>
'''return''' x[-n:] + x[:-n]
'''if''' n <= 1:
'''return''' (0,)
x = pi(n - 1) + (n - 1,)
'''return''' rotate_right('''tuple'''(x[k] '''for''' k '''in''' x), 1)
if n == 1 and j == 0:
'''if''' '''not''' reverse:
'''yield''' (0,) + x
'''for''' x '''in''' p(n - 1, j - 1, reverse=True):
'''yield''' (1,) + '''tuple'''(x[k] '''for''' k '''in''' perm) monotonic(n):<font color=green/code> // *Генерация монотонного кода Грея при помощи уже написанной сопрограммы написанного генератора p.</fontcode> monotonic(n):
'''for''' i '''in''' range(n):
'''for''' x '''in''' (p(n, i) '''if''' i % 2 == 0 '''else''' p(n, i, reverse=True)):
