Монотонный код Грея — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(не показано 16 промежуточных версий 3 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Монотонный код Грея''' (англ. ''Monotonic Gray Code'') {{---}} способ построения кода Грея, что <tex>\nexists</tex> <tex>g_i, g_j</tex>, что <tex>g_i</tex> содержит на 2 или больше единиц, чем <tex>g_j</tex>.
+
'''Монотонный код Грея''' (англ. ''Monotonic Gray Code'') {{---}} способ построения кода Грея, при котором <tex>\forall 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>1</tex> в данном двоичном коде. Очевидно, что нельзя построить [[:Коды_Грея|код Грея]] в котором бы вес всегда возрастал.
 
Неплохим решением этой проблемы будет обход всех кодов со смежными с данным весами.
 
Неплохим решением этой проблемы будет обход всех кодов со смежными с данным весами.
  
Строка 13: Строка 13:
  
 
<tex>
 
<tex>
V_n(i) = \{ v \in V_n : v \text{ has weight } i \}
+
V_n(i) = \{ v \mid v \text{ has weight } i \}
 
</tex>
 
</tex>
  
для <tex>0 \leq i \leq n</tex>. Для всех уровней выполняется соотношение <tex>|V_n(i)| = \binom{n}{i}</tex>.
+
для <tex>0 \leqslant i \leqslant n</tex>. Для всех уровней выполняется соотношение <tex>|V_n(i)| = 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(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 \in E_n(i)</tex> идет перед <tex>\delta_2 \in E_n(j)</tex>, то <tex>i \leq j</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>\forall i, j : i \leqslant j</tex>, то <tex>\delta_1 \in E_n(i)</tex> идет перед <tex>\delta_2 \in E_n(j)</tex>.
  
Ниже на катринке Гамильтонов путь в гиперкубе <tex>Q_4</tex> для <tex>n = 4</tex>, построенный по алгоритму Саважа-Винклера(англ. ''Savage-Winkler'').
+
Ниже на катринке Гамильтонов путь в гиперкубе <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-ичный монотооный код Грея]]
+
[[Файл:Monotonic_Gray_Code_Graph.png|center|4-ичный монотонный код Грея]]
  
Элегантная идея построения <tex>n</tex>-ичного монотонного кода Грея состоит в том, чтобы рекурсивно строить подпути <tex>P_{n,j}</tex> длинны <tex>2 \binom{n}{j}</tex> включающих вершины <tex>E_n(j)</tex>.
+
Элегантная идея построения <tex>n</tex>-ичного монотонного кода Грея состоит в том, чтобы рекурсивно строить подпути <tex>P_{n,j}</tex> длинны <tex>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 n</tex> и  
+
Определим <tex>P_{1,0} = (0, 1)</tex> и <tex>P_{n,j} = \emptyset</tex>, когда <tex>j < 0</tex> или <tex>j \geqslant n</tex> и  
 
<tex>
 
<tex>
 
P_{n+1,j} = 1P^{\pi_n}_{n,j-1}, 0P_{n,j}
 
P_{n+1,j} = 1P^{\pi_n}_{n,j-1}, 0P_{n,j}
</tex>.
+
</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>\pi_n</tex> это определенная перестановка элементов множества к которому она применена, а <tex>P^{\pi}</tex> это путь <tex>P</tex> к котрому была применена пересатновка  <tex>\pi</tex>.
Существует два варианта построить моготонный код грея по путям <tex>P_{n, j}</tex>.  
+
Существует два варианта построить монотонный код грея по путям <tex>P_{n, j}</tex>.  
  
 
Назовем их <tex>G_n^{(1)}</tex> и <tex>G_n^{(2)}</tex>. Будем строить их таким образом:  
 
Назовем их <tex>G_n^{(1)}</tex> и <tex>G_n^{(2)}</tex>. Будем строить их таким образом:  
 
<tex>
 
<tex>
G_n^{(1)} = P_{n,0} P_{n,1}^R P_{n,2} P_{n,3}^R \cdots \text{, } G_n^{(2)} = P_{n,0}^R P_{n,1} P_{n,2}^R P_{n,3} \cdots
+
G_n^{(1)} = P_{n,0} P_{n,1}^R P_{n,2} P_{n,3}^R \ldots \text{, } G_n^{(2)} = P_{n,0}^R P_{n,1} P_{n,2}^R P_{n,3} \ldots
 
</tex>
 
</tex>
  
Строка 70: Строка 70:
 
</center>
 
</center>
  
Монотонный код Грея может быть эффективно сгенерирован по этому алгоритму за время <tex>O(n)</tex>. Легче всего написать этот алгоритм используя сопрограмму, пример которой будет предложен ниже.
+
Монотонный код Грея может быть эффективно сгенерирован по этому алгоритму за время <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"  
 
{| border="0"  
 
|align="left" colspan="4"|
 
|align="left" colspan="4"|
 +
Вспомогательная функция для генерации перестановки, циклически сдвигает битовый вектор направо <tex>n</tex> раз.
 +
Принимает и возвращает кортеж. Кортеж аналог списка, но в кортеже нельзя менять элементы, можно только добавлять.
 +
<code>[i:]</code> {{---}} возвращает подсписок, начиная с индекса <tex>i</tex> (аналогично <code>[:i]</code>), а отрицательный знак позволяет индексироваться с конца (полагая, что -1 — последний элемент списка).
 
<code>
 
<code>
<font color = brown>rotate_right</font>(x, n):
+
'''function''' rotateRight(x: '''int[n]'''): '''int[n]'''
 
     '''return''' x[-n:] + x[:-n]
 
     '''return''' x[-n:] + x[:-n]
<font color = brown>pi</font>(n):
+
</code>
     '''if''' n <= 1:
+
Рекурсивная генерация <tex>n</tex>-ой перестановки.
 +
Возвращает перестановку в виде кортежа.
 +
Если <tex>n</tex> становится меньше <tex>2</tex> дописывает в начало кортежа <tex>0</tex> и возвращает его.
 +
<code>
 +
'''function''' pi('''int''' n): '''int[n]'''
 +
     '''if''' n <= 1
 
         '''return''' (0,)
 
         '''return''' (0,)
 
     x = pi(n - 1) + (n - 1,)
 
     x = pi(n - 1) + (n - 1,)
     '''return''' rotate_right('''tuple'''(x[k] '''for''' k '''in''' x), 1)
+
     '''return''' rotateRight('''tuple'''(x[k] '''for''' k '''in''' x), 1)
<font color = brown>p</font>(n, j, reverse=False):
+
</code>
     if n == 1 and j == 0:
+
Рекурсивная генерация пути <tex>P_{n, j}</tex>.
         '''if''' '''not''' reverse:
+
Принимает <tex>n, j</tex>, а так же дополнительный параметр определяющий надо-ли переворачивать кортеж.
 +
<code>
 +
'''function''' p('''int''' n, '''int''' j, '''bool''' reverse = ''false''): '''list<int[n]>'''
 +
     '''if''' n == 1 and j == 0
 +
         '''if''' '''not''' reverse
 
             '''yield''' (0,)
 
             '''yield''' (0,)
 
             '''yield''' (1,)
 
             '''yield''' (1,)
         '''else''':
+
         '''else'''
 
             '''yield''' (1,)
 
             '''yield''' (1,)
 
             '''yield''' (0,)
 
             '''yield''' (0,)
     '''elif''' j >= 0 '''and''' j < n:
+
     '''else if''' j >= 0 '''and''' j < n
 
         perm = pi(n - 1)
 
         perm = pi(n - 1)
         '''if''' '''not''' reverse:
+
         '''if''' '''not''' reverse
             '''for''' x '''in''' p(n - 1, j - 1):
+
             '''for''' x '''in''' p(n - 1, j - 1)
 
                 '''yield''' (1,) + '''tuple'''(x[k] '''for''' k '''in''' perm)
 
                 '''yield''' (1,) + '''tuple'''(x[k] '''for''' k '''in''' perm)
             '''for''' x '''in''' p(n - 1, j):
+
             '''for''' x '''in''' p(n - 1, j)
 
                 '''yield''' (0,) + x
 
                 '''yield''' (0,) + x
         '''else''':
+
         '''else'''
             '''for''' x '''in''' p(n - 1, j, reverse=True):
+
             '''for''' x '''in''' p(n - 1, j, reverse=''true'')
 
                 '''yield''' (0,) + x
 
                 '''yield''' (0,) + x
             '''for''' x '''in''' p(n - 1, j - 1, reverse=True):
+
             '''for''' x '''in''' p(n - 1, j - 1, reverse=''true'')
                 '''yield''' (1,) + '''tuple'''(x[k] '''for''' k '''in''' perm)  
+
                 '''yield''' (1,) + '''tuple'''(x[k] '''for''' k '''in''' perm)
<font color = brown>monotonic</font>(n):
+
</code>
     '''for''' i '''in''' range(n):
+
Генерация монотонного кода Грея при помощи уже написанного генератора <tex>p</tex>.
         '''for''' x '''in''' (p(n, i) '''if''' i % 2 == 0 '''else''' p(n, i, reverse=True)):
+
<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''))
 
             '''yield''' x
 
             '''yield''' x
 
</code>
 
</code>
Строка 141: Строка 161:
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Комбинаторика]]
 
[[Категория: Комбинаторика]]
 +
[[Категория: Комбинаторные объекты ]]

Версия 13:32, 24 июня 2019

Определение:
Монотонный код Грея (англ. Monotonic Gray Code) — способ построения кода Грея, при котором [math]\forall i \lt j[/math] [math]\nexists g_i, g_j[/math], что [math]g_i[/math] содержит на [math]2[/math] или больше единиц, чем [math]g_j[/math].

Монотонный код Грея преимущественно используется в теории связанных сетей, например для минимизации ожидания линейным массивом процессоров.[1]

Алгоритм построения

Для начала определим такое понятие, как вес двоичного кода, им будет являтся количество [math]1[/math] в данном двоичном коде. Очевидно, что нельзя построить код Грея в котором бы вес всегда возрастал. Неплохим решением этой проблемы будет обход всех кодов со смежными с данным весами.

Мы можем формализовать модель монотонных кодов Грея рассматривая разбиение гиперкуба [math]Q_n = (V_n, E_n)[/math], вершины в котором являются двоичными кодами, на уровни с одинаковым весом вершин.

[math] V_n(i) = \{ v \mid v \text{ has weight } i \} [/math]

для [math]0 \leqslant i \leqslant n[/math]. Для всех уровней выполняется соотношение [math]|V_n(i)| = C_n^i[/math].

Пусть [math]Q_n(i)[/math] подграф [math]Q_n[/math], который является объединением двух смежных уровней, т. е. [math]V_n(i) \cup V_n(i+1)[/math], и пусть [math]E_n(i)[/math] множество граней [math]Q_n(i)[/math]. Тогда монотонным кодом Грея будет являтся Гамильтонов путь в [math]Q_n[/math], при котором любое множество вершин [math]\delta_1 , \delta_2[/math] такие, что [math]\forall i, j : i \leqslant j[/math], то [math]\delta_1 \in E_n(i)[/math] идет перед [math]\delta_2 \in E_n(j)[/math].

Ниже на катринке Гамильтонов путь в гиперкубе [math]Q_4[/math] для [math]n = 4[/math], построенный по алгоритму Саважа-Винклера (англ. Savage-Winkler).[2]

4-ичный монотонный код Грея

Элегантная идея построения [math]n[/math]-ичного монотонного кода Грея состоит в том, чтобы рекурсивно строить подпути [math]P_{n,j}[/math] длинны [math]2C_n^j[/math] включающих вершины [math]E_n(j)[/math].

Определим [math]P_{1,0} = (0, 1)[/math] и [math]P_{n,j} = \emptyset[/math], когда [math]j \lt 0[/math] или [math]j \geqslant n[/math] и [math] P_{n+1,j} = 1P^{\pi_n}_{n,j-1}, 0P_{n,j} [/math]. То есть [math]P_{n+1, j}[/math] это объединение множеств [math]P^{\pi_n}_{n,j-1}[/math] с приписанной в начале [math]1[/math] и [math]P_{n,j}[/math] с приписанным в начале [math]0[/math].

Здесь [math]\pi_n[/math] это определенная перестановка элементов множества к которому она применена, а [math]P^{\pi}[/math] это путь [math]P[/math] к котрому была применена пересатновка [math]\pi[/math]. Существует два варианта построить монотонный код грея по путям [math]P_{n, j}[/math].

Назовем их [math]G_n^{(1)}[/math] и [math]G_n^{(2)}[/math]. Будем строить их таким образом: [math] G_n^{(1)} = P_{n,0} P_{n,1}^R P_{n,2} P_{n,3}^R \ldots \text{, } G_n^{(2)} = P_{n,0}^R P_{n,1} P_{n,2}^R P_{n,3} \ldots [/math]

Выбор перестановки [math]\pi_n[/math] обусловлен тем, чтобы получившиеся коды соответсвовали требованиям кода Грея и поэтому эта перестановка равна [math]\pi_n = E^{-1}(\pi_{n-1}^2)[/math].

Чтобы лучше разобратся в том, как сторится этот код и работает перестановка [math]\pi[/math] следует рассмотреть таблицу ниже.

Подпути алгоритма Саважа-Винклера
[math]P_{n,j}[/math] [math]j = 0[/math] [math]j = 1[/math] [math]j = 2[/math] [math]j = 3[/math]
[math]n = 1[/math] [math]0, 1[/math]
[math]n = 2[/math] [math]00, 01[/math] [math]10, 11[/math]
[math]n = 3[/math] [math]000, 001[/math] [math]100, 110, 010, 011[/math] [math]101, 111[/math]
[math]n = 4[/math] [math]0000, 0001[/math] [math]1000, 1100, 0100, 0110, 0010, 0011[/math] [math]1010, 1011, 1001, 1101, 0101, 0111[/math] [math]1110, 1111[/math]

Монотонный код Грея может быть эффективно сгенерирован по этому алгоритму за время [math]O(n)[/math]. Легче всего написать этот алгоритм используя генератор.

Псевдокод

Перед тем как писать псевдокод необходимо объяснить что такое yield и что понимать под выражениями типа (0,) или (1,).

yield — аналог return только для функций-генераторов. То есть генераторы это тоже итерируемые объекты, но прочитать их можно лишь один раз. Это связано с тем, что они не хранят значения в памяти, а генерируют их на лету.

С конструкциями типа (0,) или (1,) все проще. Используя ее совместно с yield мы можем изменять наш генерируемый объект. Например, yield (0,) допишет к генерируемому объекту (в нашем случае кортежу (англ. tuple)) [math]0[/math] в начало.

Вспомогательная функция для генерации перестановки, циклически сдвигает битовый вектор направо [math]n[/math] раз. Принимает и возвращает кортеж. Кортеж аналог списка, но в кортеже нельзя менять элементы, можно только добавлять. [i:] — возвращает подсписок, начиная с индекса [math]i[/math] (аналогично [:i]), а отрицательный знак позволяет индексироваться с конца (полагая, что -1 — последний элемент списка).

function rotateRight(x: int[n]): int[n]
   return x[-n:] + x[:-n]

Рекурсивная генерация [math]n[/math]-ой перестановки. Возвращает перестановку в виде кортежа. Если [math]n[/math] становится меньше [math]2[/math] дописывает в начало кортежа [math]0[/math] и возвращает его.

function pi(int n): int[n]
   if n <= 1
       return (0,)
   x = pi(n - 1) + (n - 1,)
   return rotateRight(tuple(x[k] for k in x), 1)

Рекурсивная генерация пути [math]P_{n, j}[/math]. Принимает [math]n, j[/math], а так же дополнительный параметр определяющий надо-ли переворачивать кортеж.

function p(int n, int j, bool reverse = false): list<int[n]>
   if n == 1 and j == 0
       if not reverse
           yield (0,)
           yield (1,)
       else
           yield (1,)
           yield (0,)
   else 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)

Генерация монотонного кода Грея при помощи уже написанного генератора [math]p[/math].

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))
           yield x

Визуализация работы алгоритма

Для [math]n = 5[/math]

Визуализация работы алгоритма для 5-ичного кода

Для [math]n = 6[/math]

Визуализация работы алгоритма для 6-ичного кода

См. Также

Примечания

Источники информации