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

код Грея для перестановки при n = 2 1 2 2 1

код Грея для перестановки при n = 3 1 2 3 2 1 3 2 3 1 3 2 1 3 1 2 1 3 2

код Грея для перестановки при n = 4 1 2 3 4 2 1 3 4 2 3 1 4 2 3 4 1 3 2 4 1 3 2 1 4 3 1 2 4 1 3 2 4 1 3 4 2 3 1 4 2 3 4 1 2 3 4 2 1 4 3 2 1 4 3 1 2 4 1 3 2 1 4 3 2 1 4 2 3 4 1 2 3 4 2 1 3 4 2 3 1 2 4 3 1 2 4 1 3 2 1 4 3 1 2 4 3

Определение

Коды Грея для перестановок - называют такое упорядочение перестановок, что соседние перестановки отличаются только элементарной транспозицией.

Построения Кода Грея для перестановок на Pascal

for i := 1 to n do
  begin
   P[i] := i;
   C[i] := 1;
   PR[i] := true;
  end;
C[n] := 0;
for g := 1 to n do
  write(P[g], ' ');
writeln;
i := 1;
while i < n do
  begin
    i := 1;
    x := 0;
    while C[i] = n - i + 1 do
      begin
        PR[i] := not PR[i];
        C[i] := 1;
        if PR[i] then x := x + 1;
        i := i + 1;
      end;
    if i < n then
      begin
        if PR[i] then k := C[i] + x
          else k := n - i + 1 - C[i] + x;
        swap(P[k], P[k + 1]);
        for g := 1 to n do
          write(P[g], ' ');
        writeln;
        C[i] := C[i] + 1
      end;
  end;