Материал: 00464

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

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

Решение. Наряду с множеством перестановок рассмотрим множество последовательностей y[1]..y[n] целых неотрицательных чисел, для которых , , . В нем столько же элементов, сколько в множестве всех перестановок, и мы сейчас установим между ними взаимно однозначное соответствие. Именно, каждой перестановке поставим в соответствие последовательность 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 ; это можно облегчить, если помимо самой перестановки хранить функцию

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

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.

Лекция 6. Применение методов комбинаторного перебора.

Посмотрим еще раз на использованные нами приемы. Вначале удавалось решить задачу по такой схеме: определяем порядок на подлежащих перечислению объектах и явно описываем процедуру перехода от данного объекта к следующему (в смысле этого порядка). В задаче о кодах Грея потребовалось хранить, помимо текущего объекта, и некоторую дополнительную информацию (направления стрелок). Наконец, в задаче о перечислении перестановок (на каждом шаге допустима одна транспозиция) мы применили такой прием: установили взаимно однозначное соответствие между перечисляемым множеством и другим, более просто устроенным. Таких соответствий в комбинаторике известно много. Мы приведем несколько задач, связанных с так называемыми " числами Каталана ".

Перечислить все последовательности длины 2n, составленные из n единиц и n минус единиц, у которых сумма любого начального отрезка неотрицательна, т.е. число минус единиц в нем не превосходит числа единиц. (Число таких последовательностей называют числом Каталана ; формулу для чисел Каталана см. в следующем разделе.)

Решение. Изображая единицу вектором (1,1), а минус единицу вектором (1,-1), можно сказать, что мы ищем пути из точки (0,0) в точку (n,0), не опускающиеся ниже оси абсцисс.

Будем перечислять последовательности в лексикографическом порядке, считая, что -1 предшествует 1. Первой последовательностью будет "пила"

а последней - "горка"

Как перейти от последовательности к следующей? До некоторого места они должны совпадать, а затем надо заменить -1 на 1. Место замены должно быть расположено как можно правее. Но заменять -1 на 1 можно только в том случае, если справа от нее есть единица (которую можно заменить на -1 ). После замены -1 на 1 мы приходим к такой задаче: фиксирован начальный кусок последовательности, надо найти минимальное продолжение. Ее решение: надо приписывать -1, если это не нарушит условия неотрицательности, а иначе приписывать 1. Получаем такую программу:

...

type array2n = array [1..2n] of integer;

...

procedure get_next (var a: array2n; var last: Boolean);

| {в a помещается следующая последовательность, если}

| {она есть (при этом last:=false), иначе last:=true}

| var k, i, sum: integer;

begin

| k:=2*n;

| {инвариант: в a[k+1..2n] только минус единицы}

| while a[k] = -1 do begin k:=k-1; end;

| {k - максимальное среди тех, для которых a[k]=1}

| while (k>0) and (a[k] = 1) do begin k:=k-1; end;

| {a[k] - самая правая -1, за которой есть 1;

| если таких нет, то k=0}

| if k = 0 then begin

| | last := true;

| end else begin

| | last := false;

| | i:=0; sum:=0;

| | {sum = a[1]+...+a[i]}

| | while i< >k do begin

| | | i:=i+1; sum:= sum+a[i];

| | end;

| | {sum = a[1]+...+a[k], a[k]=-1}

| | a[k]:= 1; sum:= sum+2;

| | {вплоть до a[k] все изменено, sum=a[1]+...+a[k]}

| | while k < > 2*n do begin

| | | k:=k+1;

| | | if sum > 0 then begin

| | | | a[k]:=-1

| | | end else begin

| | | | a[k]:=1;

| | | end;

| | | sum:= sum+a[k];

| | end;

| | {k=2n, sum=a[1]+...a[2n]=0}

| end;

end;

Перечислить все расстановки скобок в произведении n сомножителей. Порядок сомножителей не меняется, скобки полностью определяют порядок действий. Например, для n=4 есть 5 расстановок:

Указание. Каждому порядку действий соответствует последовательность команд стекового калькулятора, описанного в пункте 8.3.

На окружности задано 2n точек, пронумерованных от 1 до 2n. Перечислить все способы провести n непересекающихся хорд с вершинами в этих точках.

Перечислить все способы разрезать n -угольник на треугольники, проведя n-2 его диагонали.

(Мы вернемся к разрезанию многоугольника в разделе о динамическом программировании, пункт 8.1.)

Еще один класс задач на перечисление всех элементов заданного множества мы рассмотрим ниже, обсуждая метод поиска с возвратами (backtracking).

Подсчет количеств

Иногда можно найти количество объектов с тем или иным свойством, не перечисляя их. Классический пример: - число всех -элементных подмножеств -элементного множества - можно найти, заполняя таблицу по формулам

или по формуле

(Первый способ эффективнее, если надо вычислить много значений .)

Приведем другие примеры.

Число разбиений; предлагалась на Всесоюзной олимпиаде по программированию 1988 года. Пусть - число разбиений целого положительного на целые положительные слагаемые (без учета порядка, и - одно и то же разбиение). При положим (единственное разбиение не содержит слагаемых). Построить алгоритм вычисления для заданного .

Решение. Можно доказать (это нетривиально) такую формулу для :

(знаки у пар членов чередуются, вычитаемые в одной паре равны и ; сумма конечна - мы считаем, что при ).

Однако и без ее использования можно придумать способ вычисления , который существенно эффективнее перебора и подсчета всех разбиений.

Обозначим через (для , ) число разбиений на целые положительные слагаемые, не превосходящие . (При этом считаем равным для всех .) Очевидно, . Все разбиения на слагаемые, не превосходящие , разобьем на группы в зависимости от максимального слагаемого (обозначим его ). Число равно сумме (по всем от до ) количеств разбиений со слагаемыми не больше и максимальным слагаемым, равным . А разбиения на слагаемые не более с первым слагаемым, равным , по существу представляют собой разбиения на слагаемые, не превосходящие (при ). Так что