Изменения

Перейти к: навигация, поиск

Монотонный код Грея

3601 байт добавлено, 13:32, 24 июня 2019
м
Нет описания правки
{{Определение
|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>
== Алгоритм построения ==
Для начала определим такое понятие, как ''вес'' двоичного кода, им будет являтся количество <tex>1</tex> в данном двоичном коде. Очевидно, что нельзя построить [[:Коды_Грея|код Грея ]] в котором бы вес всегда возрастал.
Неплохим решением этой проблемы будет обход всех кодов со смежными с данным весами.
<tex>
V_n(i) = \{ v \in V_n : mid 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>.Тогда монотонным кодом Грея будет являтся [[:Гамильтоновы_графы#.D0.9E.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|Гамильтонов путь ]] в <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>n</tex>-ичного монотонного кода Грея состоит в том, чтобы рекурсивно строить подпути <tex>P_{n,j}</tex> длинны <tex>2 \binom{n}{2C_n^j}</tex> включающих вершины <tex>E_n(j)</tex>.
Определим <tex>P_{1,0} = (0, 1)</tex> и <tex>P_{n,j} = \emptyset</tex>, когда <tex>j < 0</tex> или <tex>j \geq geqslant n</tex> и
<tex>
P_{n+1,j} = 1P^{\pi_n}_{n,j-1}, 0P_{n,j}
</tex>. То есть <tex>P_{n+1, j}</tex> это объединение множеств <tex>P^{\pi_n}_{n,j-1}</tex> с приписанной в начале <tex>1</tex> и <tex>P_{n,j}</tex> с приписанным в начале <tex>0</tex>.
Здесь <tex>\pi_n</tex> это определенная перестановка элементов множества к которому она применена, а <tex>P^{\pi}</tex> это путь <tex>P</tex> к котрому была применена пересатновка <tex>\pi</tex>.
Существует два варианта построить моготонный монотонный код грея по путям <tex>P_{n, j}</tex>.
Назовем их <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>
</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>[i:]</code> {{---}} возвращает подсписок, начиная с индекса <tex>i</tex> (аналогично <code>[:i]</code>), а отрицательный знак позволяет индексироваться с конца (полагая, что -1 — последний элемент списка).
<code>
<font color = brown>rotate_right</font> '''function''' rotateRight(x, : '''int[n]'''):'''int[n]'''
'''return''' x[-n:] + x[:-n]
<font color = brown/code>Рекурсивная генерация <tex>n</tex>-ой перестановки. Возвращает перестановку в виде кортежа. Если <tex>n</tex> становится меньше <tex>2</tex> дописывает в начало кортежа <tex>pi0</fonttex> и возвращает его.<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)<font color = brown/code>Рекурсивная генерация пути <tex>P_{n, j}</tex>. Принимает <tex>pn, j</fonttex>, а так же дополнительный параметр определяющий надо-ли переворачивать кортеж.<code> '''function''' p('''int''' n, '''int''' j, '''bool''' reverse=False''false''):'''list<int[n]>''' '''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''true''):
'''yield''' (0,) + x
'''for''' x '''in''' p(n - 1, j - 1, reverse=True''true''): '''yield''' (1,) + '''tuple'''(x[k] '''for''' k '''in''' perm) <font color = brown/code>Генерация монотонного кода Грея при помощи уже написанного генератора <tex>monotonicp</fonttex>.<code> '''function''' monotonic('''int''' n):'''list<int[n]>''' '''for''' i '''in''' range(n): '''for''' x '''in''' (p(n, i) '''if''' i % 2 == 0 '''else''' p(n, i, reverse=True''true'')):
'''yield''' x
</code>
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Коды Грея]][[Категория: Комбинаторные объекты]]
6
правок

Навигация