162
правки
Изменения
Нет описания правки
{{Определение
|definition =
'''Монотонный код Грея''' (англ. ''Monotonic Gray Code'') {{---}} способ построения кода Грея, при котором <tex>\nexistsforall i < j</tex> <tex>\nexists g_i, g_j</tex>, что <tex>g_i</tex> содержит на <tex>2</tex> или больше единиц, чем <tex>g_j</tex>.
}}
Монотонный код Грея преимущественно используется в теории связанных сетей, например для минимизации ожидания линейным массивом процессоров.<ref>[http://www.sciencedirect.com/science/article/pii/0097316595900918 C. D Savage and P. Winkler (1995). "Monotone Gray codes and the middle levels problem"page 7]</ref>
Перед тем как писать псевдокод необходимо объяснить что такое <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"|
<code>
'''function''' rotateRight(x, : '''int[n]'''):'''int[n]'''
'''return''' x[-n:] + x[:-n]
</code>
<code>
'''function''' pi('''int''' n):'''int[n]''' '''if''' n <= 1:
'''return''' (0,)
x = pi(n - 1) + (n - 1,)
'''return''' rotate_rightrotateRight('''tuple'''(x[k] '''for''' k '''in''' x), 1)
</code>
<code>
'''function''' p('''int''' n, '''int''' j, '''bool''' reverse = ''false''): '''if ''' n == 1 and j == 0: '''if''' '''not''' reverse:
'''yield''' (0,)
'''yield''' (1,)
'''else''':
'''yield''' (1,)
'''yield''' (0,)
'''elifelse if''' j >= 0 '''and''' j < n:
perm = pi(n - 1)
'''if''' '''not''' reverse: '''for''' x '''in''' p(n - 1, j - 1):
'''yield''' (1,) + '''tuple'''(x[k] '''for''' k '''in''' perm)
'''for''' x '''in''' p(n - 1, j):
'''yield''' (0,) + x
'''else''': '''for''' x '''in''' p(n - 1, j, reverse=True):
'''yield''' (0,) + x
'''for''' x '''in''' p(n - 1, j - 1, reverse=True):
'''yield''' (1,) + '''tuple'''(x[k] '''for''' k '''in''' perm)
</code>
<code>
'''function''' monotonic('''int''' n): '''for''' i '''in''' range(n): '''for''' x '''in''' (p(n, i) '''if''' i % 2 == 0 '''else''' p(n, i, reverse=True)):
'''yield''' x
</code>
