Изменения

Перейти к: навигация, поиск

Коды Грея для перестановок

361 байт добавлено, 04:21, 28 декабря 2011
Нет описания правки
== Псевдокод получения следующего кода Грея ==
Пусть нам известен код Грея для длины $n - 1$, записанный в массив из строк $sperm[i](j)$, где $i$ - номер перестановки , а $j$ номера элементов перестановок(номерация начинается с единицы, элементы разделены пробелами). При этом переменная $t = true$, $j = 1$, а $k$ является новым элементом:
procedure grey_code(t: boolean; j: integer);
var
str: string; i, c: integer;
begin
if j <= (n - 1)! then {условие выхода из рекурсии}
if t = true then
begin
str for l := k + ' ' + s[j]; n - 1 downto 1 do {записываем элемент n в начало строки} perm[j](l + 1) := perm[j](l); perm[j](1) := n; for l := 1 to n do writeln(strperm[j](1), ' '); {выводим перестановку}
for i := 0 to n - 2 do
begin
c := strperm[2 * j](i + 1]); {меняем элементы местами и выводим каждую новую перестановку} strperm[2 * j](i + 1] ) := strperm[2 * j](i + 3]1); strperm[2 * j](i + 3] 1) := c; for l := 1 to n do writeln(strperm[j](1), ' '); {выводим перестановку}
end;
grey_code(not t, j + 1); {повторяем процедуру}
else
begin
str := sperm[j] + ' ' + k(n) := n; {записываем элемент n в конец строки} for l := 1 to n do writeln(strperm[j](1), ' '); {выводим перестановку}
for i := n - 2 downto 0 do
begin
c := strperm[2 * j](i + 1]); {меняем элементы местами и выводим каждую новую перестановку} strperm[2 * j](i + 1] ) := strperm[2 * j](i + 3]1); strperm[2 * j](i + 3] 1) := c; for l := 1 to n do writeln(strperm[j](1), ' '); {выводим перестановку}
end;
grey_code(not t, j + 1); {повторяем процедуру}
94
правки

Навигация