152
правки
Изменения
Нет описания правки
for i := 1 to n do
begin
P[i] := i;//перестановка C[i] := 1;//показывает, какую из возможных n - i + 1 позиций i занимает относительно элементов i + 1, .., n PR[i] := true;//содержит информацию о том, переносился ли элемент i вперед или назад
end;
C[n] := 0;
for g := 1 to n - 1 do
write(P[g], ' ');
writeln(P[n]);
i := 1;
while i < n do
if PR[i] then k := C[i] + x
else k := n - i + 1 - C[i] + x;
swap(P[k], P[k + 1]);// меняем местами значения P[k] и P[k + 1] for g := 1 to n - 1 do
write(P[g], ' ');
writeln(P[n]);
C[i] := C[i] + 1
end;
end;
== '''Сведение задачи построение кода Грея для перестановок к графам''' ==
Последовательность перестановок, полученная с помощью данного алгоритма имеет интересную интерпретацию. Так, если рассмотреть граф, вешины которого соответствуют всем перестановкам и в котором две вершины, соответствующие перестановкам f и g, соединены ребром, если g образуется из f однократной транспозицией соседних элементов, то полученная последовательность является гамильтоновым путем в этом графе. На рисунке изображен граф последовательности для n = 3, 4.
