94
правки
Изменения
Нет описания правки
== Примеры кодов Грея для перестановок ==
{| border="1" | $n=2:$ | $n=3:$ |- | $\{1, 2\}$ | $\{1, 2, 3\}$ |- | $\{2, 1\}$ | $\{1, 3, 2\}$ |- | $\{3, 1, 2\}$ |- | $\{3, 2, 1\}$ |- | $\{2, 3, 1\}$ |- | $\{2, 1, 3\}$|}
== Построение кода Грея для перестановок ==
Для $n = 1$ код Грея выглядит так:
$\{ 1 \}$ {{---}} $n!$ различных перестановок, отличных друг от друга в одной транспозиции (очевидно).
Будем строить код Грея для перестановок длины $n = k$. Предположим, что нам известен код Грея для перестановок длиной $n = k - 1$. Возьмем первую перестановку из известного нам кода. Пусть она выглядит так:
Пусть нам известен код Грея для длины $n-1$, записанный в массив pred_perest[i](j), где $i$ - номер перестановки, $j$ - номер элемента этой перестановки (номерация начинается с единицы).
t := false;
for i := 1 to (n-1)! - do for k:=1 to n do
begin
if t = true then
for j := 1 to n-1 do
begin
pomestit_v (pred_prest[i], t);
l := pred_perest[i](j+1);
pred_perest[i](j+1) := pred_perest[i](j);
for j := n-1 downto 1 do
begin
pomestit_v (pred_prest[i], t);
l := pred_perest[i](j+1);
pred_perest[i](j+1) := pred_perest[i](j);
