94
правки
Изменения
Нет описания правки
<wikitex>
== Определения ==
{{Определение
|definition=
Последовательность перестановок, полученная с помощью данного алгоритма имеет интересную интерпретацию. Так, если рассмотреть граф, вершины которого соответствуют всем перестановкам и в котором две вершины, соответствующие перестановкам $f$ и $g$, соединены ребром, если $g$ образуется из $f$ однократной транспозицией соседних элементов, то полученная последовательность является гамильтоновым путем в этом графе.
== Псевдокод получения следующего кода Грея ==
Пусть нам известен код Грея для длины $n-1$, записанный в массив pred_perest[i](j), где $i$ - номер перестановки, $j$ - номер элемента этой перестановки (номерация начинается с единицы).
pred_perest[1](n) := n;
t := false;
for i := 1 to (n-1)! - 1 do
begin
if t = true then
for j := 1 to n-1 do
begin
l := pred_perest[i](j+1);
pred_perest[i](j+1) := pred_perest[i](j);
pred_perest[i](j) := l;
t := false;
writeln(pred_perest[i]);
end
else
for j := n-1 downto 1 do
begin
l := pred_perest[i](j+1);
pred_perest[i](j+1) := pred_perest[i](j);
pred_perest[i](j) := l;
t := true;
writeln(pred_perest[i]);
end;
end;
== См. также ==
