Задача 98835

Тема:    [ Нерекурсивная генерация объектов ]

Сложность: 4 Классы:

Условие

Напечатать все перестановки чисел 1..n так, чтобы каждая следующая получалась из предыдущей перестановкой (транспозицией) двух соседних чисел. Например, при n=3 допустим такой порядок:

3.2 1  2 3.1  2.1 3  1 2.3  1.3 2  3 1 2

(между переставляемыми числами вставлены точки).

Решение

Наряду с множеством перестановок рассмотрим множество последовательностей y[1]..y[n] целых неотрицательных чисел, для которых y[1]0, ..., y[n]n-1. В нём столько же элементов, сколько в множестве всех перестановок, и мы сейчас установим между ними взаимно однозначное соответствие. Именно, каждой перестановке поставим в соответствие последовательность y[1]..y[n], где y[i] — количество чисел, меньших i и стоящих левее i в этой перестановке. Взаимная однозначность вытекает из такого замечания. Перестановка чисел 1..n получается из перестановки чисел 1..n-1 добавлением числа n, которое можно вставить на любое из n мест. При этом к сопоставляемой с ней последовательности добавляется ещё один член, принимающий значения от 0 до n-1, а предыдущие члены не меняются. При этом оказывается, что изменение на единицу одного из членов последовательности y соответствует транспозиции двух соседних чисел, если все следующие числа последовательности y принимают максимально или минимально возможные для них значения. Именно, увеличение y[i] на 1 соответствует транспозиции числа i с его правым соседом, а уменьшение — с левым. Теперь вспомним решение задачи о перечислении всех последовательностей, на каждом шаге которого один член меняется на единицу. Заменив прямоугольную доску доской в форме лестницы (высота i-ой вертикали равна i) и двигая шашки по тем же правилам, мы перечислим все последовательности y, причём i-ый член будет меняться как раз только если все следующие шашки стоят у края. Надо ещё уметь параллельно с изменением y корректировать перестановку. Очевидный способ требует отыскания в ней числа i; это можно облегчить, если помимо самой перестановки хранить функцию

i  позиция числа i в перестановке,

--е обратное к перестановке отображение, и соответствующим образом её корректировать. Вот какая получается программа:

        program test;
        | const n=...;
        | var
        |   x: array [1..n] of 1..n; {перестановка}
        |   inv_x: array [1..n] of 1..n; {обратная перестановка}
        |   y: array [1..n] of integer; {y[i] < i}
        |   d: array [1..n] of -1..1; {направления}
        |   b: boolean;
        |
        | procedure print_x;
        | | var i: integer;
        | begin
        | | for i:=1 to n do begin
        | | | write (x[i], ' ');
        | | end;
        | | writeln;
        | end;
        |
        | procedure set_first;{первая: y[i]=0 при всех i}
        | | var i : integer;
        | begin
        | | for i := 1 to n do begin
        | | | x[i] := n + 1 - i;
        | | | inv_x[i] := n + 1 - i;
        | | | y[i]:=0;
        | | | d[i]:=1;
        | | end;
        | end;
        |
        | procedure move (var done : boolean);
        | | var i, j, pos1, pos2, val1, val2, tmp : integer;
        | begin
        | | i := n;
        | | while (i > 1) and (((d[i]=1) and (y[i]=i-1)) or
        | | |          ((d[i]=-1) and (y[i]=0))) do begin
        | | | i := i-1;
        | | end;
        | | done := (i>1); {упрощение: первый член нельзя менять}
        | | if done then begin
        | | | y[i] := y[i]+d[i];
        | | | for j := i+1 to n do begin
        | | | | d[j] := -d[j];
        | | | end;
        | | | pos1 := inv_x[i];
        | | | val1 := i;
        | | | pos2 := pos1 + d[i];
        | | | val2 := x[pos2];
        | | | {pos1, pos2 - номера переставляемых элементов;
        | | |   val1, val2 - их значения; val2 < val1}
        | | | tmp := x[pos1];
        | | | x[pos1] := x[pos2];
        | | | x[pos2] := tmp;
        | | | tmp := inv_x[val1];
        | | | inv_x[val1] := inv_x[val2];
        | | | inv_x[val2] := tmp;
        | | end;
        | end;
        |
        begin
        | set_first;
        | print_x;
        | b := true;
        | {напечатаны все перестановки до текущей включительно;
        |   если b ложно, то текущая - последняя}
        | while b do begin
        | | move (b);
        | | if b then print_x;
        | end;
        end.

Источники и прецеденты использования

книга
Автор	А.Шень
Название	Программирование: теоремы и задачи
Издательство	МЦНМО
Издание	второе
Год издания	2004
глава
Номер	2
Название	Порождение комбинаторных объектов
параграф
Номер	5
Название	Коды Грея и аналогичные задачи
задача
Номер	2.5.2