162
правки
Изменения
Нет описания правки
'''Монотонный код Грея''' (англ. ''Monotonic Gray Code'') {{---}} способ построения кода Грея, при котором <tex>\nexists</tex> <tex>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>
== Алгоритм построения ==
Для начала определим такое понятие, как ''вес'' двоичного кода, им будет являтся количество <tex>1</tex> в данном двоичном коде. Очевидно, что нельзя построить [[:Коды_Грея|код Грея ]] в котором бы вес всегда возрастал.
Неплохим решением этой проблемы будет обход всех кодов со смежными с данным весами.
<tex>
V_n(i) = \{ v \in mid V_n : v \text{ has weight } i \}
</tex>
для <tex>0 \leq leqslant i \leq leqslant n</tex>. Для всех уровней выполняется соотношение <tex>|V_n(i)| = \binom{n}{C_n^i}</tex>.
Пусть <tex>Q_n(i)</tex> подграф <tex>Q_n</tex>, который является обединением двух смежных уровней, т. е. <tex>V_n(i) \cup V_n(i+1)</tex>, и пусть <tex>E_n(i)</tex> множество граней <tex>Q_n(i)</tex>.
Тогда монотонным кодом Грея будет являтся [[:Гамильтоновы_графы|Гамильтонов путь ]] в <tex>Q_n</tex>, при котором любой любое множество вершин <tex>\delta_1 , \delta_2</tex> такие, что <tex>\in E_n(forall i, j : i)\leqslant j</tex> идет перед , то <tex>\delta_2 delta_1 \in E_n(ji)</tex>, то идет перед <tex>i \leq delta_2 \in E_n(j)</tex>.
Ниже на катринке Гамильтонов путь в гиперкубе <tex>Q_4</tex> для <tex>n = 4</tex>, построенный по алгоритму Саважа-Винклера(англ. ''Savage-Winkler'').<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 14]</ref>
[[Файл:Monotonic_Gray_Code_Graph.png|center|4-ичный монотооный код Грея]]
Назовем их <tex>G_n^{(1)}</tex> и <tex>G_n^{(2)}</tex>. Будем строить их таким образом:
<tex>
G_n^{(1)} = P_{n,0} P_{n,1}^R P_{n,2} P_{n,3}^R \cdots ldots \text{, } G_n^{(2)} = P_{n,0}^R P_{n,1} P_{n,2}^R P_{n,3} \cdotsldots
</tex>
|align="left" colspan="4"|
<code>
rotateRight(x, n):<font color = browngreen>rotate_right// Вспомогательная функция для генерации перестановки, циклически сдвигает битовый вектор направо <tex>n</fonttex>раз. Принимает и возвращает котреж (x, nангл. ''tuple''):.</font>
'''return''' x[-n:] + x[:-n]
pi(n):<font color = browngreen>pi// Рекурсивная генерация <tex>n</tex>-ой перестановки. Возвращает перестановку в виде кортежа. Если n становится меньше <tex>2</tex> дописывает в начало кортежа <tex>0</tex> и возвращает его.</font>(n):
'''if''' n <= 1:
'''return''' (0,)
x = pi(n - 1) + (n - 1,)
'''return''' rotate_right('''tuple'''(x[k] '''for''' k '''in''' x), 1)
p(n, j, reverse = ''false''):<font color = browngreen> // Рекурсивная генерация пути <tex>pP_{n, j}</fonttex>. Принимает <tex>(n, j</tex>, reverse=False):а так же дополнительный параметр определяющий надо-ли переворачивать кортеж.</font>
if n == 1 and j == 0:
'''if''' '''not''' reverse:
'''for''' x '''in''' p(n - 1, j - 1, reverse=True):
'''yield''' (1,) + '''tuple'''(x[k] '''for''' k '''in''' perm)
monotonic(n):<font color = browngreen>monotonic// Генерация монотонного кода Грея при помощи уже написанной сопрограммы p.</font>(n):
'''for''' i '''in''' range(n):
'''for''' x '''in''' (p(n, i) '''if''' i % 2 == 0 '''else''' p(n, i, reverse=True)):
