130
правок
Изменения
→Псевдокод получения кода Грея
gray_code(n):
'''if''' n == 1:
'''return''' [{1}]<font color=darkgreen>// возращаем список из одной перестановки</font color=darkgreen>
'''else''':
result = []<font color=darkgreen>// пустой список</font color=darkgreen> perms = gray_code(n - 1)<font color=darkgreen>// perms {{---}} перестановки из n - 1 элемента</font color=darkgreen> backward = false<font color=darkgreen>// переменная которая говорит откуда заполнять перестановку</font color=darkgreen> '''for''' perm in perms:<font color=darkgreen>// perm {{---}} текущая перестановка</font color=darkgreen>
'''if''' backward:
current = concat(perm, {n})<font color=darkgreen>// дописываем {n} в конец perm</font color=darkgreen> result.append(current)<font color=darkgreen>// добавляем в ответ перестановку current</font color=darkgreen>
'''for''' (i = n; i > 1; i--):
swap(current[i - 1], current[i])<font color=darkgreen>//переставляем n</font color=darkgreen> result.append(current)<font color=darkgreen>//добавляем в ответ перестановку current</font color=darkgreen>
'''else''':
current = concat({n}, perm)<font color=darkgreen>// дописываем {n} в начало perm</font color=darkgreen> result.append(current)<font color=darkgreen>//добавляем в ответ перестановку current</font color=darkgreen>
'''for''' (i = 1; i < n; i++):
swap(current[i], current[i + 1])<font color=darkgreen>//переставляем n</font color=darkgreen> result.append(current)<font color=darkgreen>//добавляем в ответ перестановку current</font color=darkgreen> backward = !backward<font color=darkgreen>//меняем состояние backward</font color=darkgreen> '''return''' result<font color=darkgreen>//возвращаем ответ в виде списка</font color=darkgreen>
== Сведение задачи построения кода Грея для перестановок к графам ==
