Перестановки (рекурсивный алгоритм)

Переборные задачи

На практике неоднократно встречаются задачи, где требуется обработать (пере­брать) все элементы некоторого конечного множества. В простейших слу­чаях элемент множества можно представить числом. При­мер такой задачи — по­иск заданного числа в одномерном массиве. Здесь для указа­ния элемента массива достаточно задать его индекс.

Более слож­ные случаи, когда элементы интересую­щего нас множества сами имеют некото­рую структуру. (Именно такие задачи обычно относят к переборным.) Во многих случаях элементы множества естест­венно записывать в виде последовательно­сти чисел фиксированного или перемен­ного размера. Очень многие переборные задачи можно свести к перебору последова­тельно­стей.

В некоторых задачах (см. например, задачу о коммивоя­жере в главе 1) требу­ется генерировать последовательности путем всевозмож­ных перестановок компо­нент некоторой заданной последовательности фиксирован­ной длины. Правила генерации последовательностей могут меняться в за­висимости от задачи:

· случайным образом,

· в лексикографическом порядке,

· пу­тем различных сочетаний компонент

· и т. п.

Примером такой задачи (в действительно­сти она эквивалентна задаче пере­бора последовательностей) явля­ется задача прохождения (обхода) деревьев. Де­рево — это граф без циклов, в кото­ром выделена одна вершина, называемая кор­нем. Для каждой вершины де­рева существует единственный путь в нее из корня. Задача состоит в том, чтобы «обойти» все вершины дерева. Если перенумеровать все ребра, выходящие из каж­дой вершины, то путь из корня, однозначно сопоставляе­мый каждой вершине, можно будет в свою очередь задать с помощью по­следовательности номеров проходи­мых ребер. Лексикографический порядок перебора последовательностей отвечает способу прохождения дерева, известному как перебор в глубину. Нахо­дясь в какой-либо вершине, мы сначала пытаемся пойти «в глубину», т. е. уда­литься от корня; если это невозможно, то мы возвраща­емся назад и пытаемся пойти в глубину по следующему ребру.

Многие практические задачи сводятся к отысканию минимума (максимума) некоторой функции на множестве. Искомым элементом множества часто является функция от времени (например, ищется закон управления самолетом, обеспечиваю­щий наибыстрейшее достижение заданной высоты и скорости). Эту функцию аппроксимируют последователь­ностью ее значений в дискретные мо­менты времени, получая задачу поиска минимума в множестве последовательно­стей. Можно осуществить поиск минимума путем полного перебора всех допусти­мых последовательностей. Метод динамического программирования позво­ляет в ряде случаев сократить перебор. Рассмот­рим несколько типичных примеров генерации последовательностей и работы с ними при решении переборных задач.

Полный перебор.

Во многих прикладных задачах требуется найти оптимальное решение среди очень большого (но конечного!) числа вариантов. Иногда удается построить это решение сразу, но в большинстве случаев единственный способ его отыскать состоит в пе­реборе всех возможных вариантов и сравнении их между собой.

Для решения переборных задач обычно используются разновидности следую­щей схемы программы:

Схема 1

Var x:элемент множества;

x:= первый элемент;

обработать x;
While x<> последний элемент Do Begin
x: =следующий за x;

обработать x;

End;

 

Иногда удается добавить к множеству еще один, фиктивный элемент, не подле­жащий обработке, который располагается перед первым обрабатываемым элементом, либо вслед за последним В этом случае обработку первого элемента можно выполнить наряду со всеми в цикле:

 

Схема 2 Схема 3

x:=фиктивный элемент; x:=первый элемент;

Repeat Repeat

x:=следующий за x; обработать x;

обработать x; x:=следующий за x;

Until x = последний элемент; Until x = фиктивный элемент;

Для конкретизации этих схем необходимо ответить на два вопроса.

1. Как будут записываться в программе элементы множества
(тип элемент множества)?

2. В каком порядке мы будем перебирать их (инструкция x:=следующий за x;)?

Рассмотрим пример. Подсчитать число счастливых билетов, т. е. таких набо­ров из шести цифр А,B,C,D,E,F, что A+B+C=D+E+F. Будем ре­шать задачу путем перебора всех комбинаций из шести цифр (это решение далеко не самое эффек­тивное). Таким образом, элемент множества задается последова­тель­но из шести цифр, каждая из которых принимает значения от 0 до 9. Для хране­ния этой последовательности используем шесть отдельных переменных. В данном случае можно, не следуя буквально введенным выше схемам, организо­вать перебор с помо­щью шести вложенных циклов FOR:

 

Program Happy_Ticket;

Var A,B,C,D,E,F,k:Integer; { k – число найденных счастливых билетов}

Begin

k:=0;

For A:=0 To 9 Do

For B:=0 To 9 Do

For C:=0 To 9 Do

For D:=0 To 9 Do

For E:=0 To 9 Do

For F:=0 To 9 Do

If A+B+C = D+E+F Then k:=k+1;

Writeln(‘ЧИСЛО СЧАСТЛИВЫХ БИЛЕТОВ=’,k);

End.

Кстати сказать, счастливых билетов 55252 (если считать и 000000), что состав­ляет примерно 1/18 общего числа билетов.

 

Последовательности.

Важно научиться строить алгоритмы перебора различных комбинатор­ных объектов - последовательностей, перестановок, подмножеств и т.д.

Схема перебора всегда будет одинакова:

· во-первых, надо установить порядок на элементах, подлежащих перечислению (в частности, определить, какой из них будет первым, а какой последним);

· во-вторых, научиться переходить от произвольного элемента к непосредственно следующему за ним (т.е. для заданного элемента x1 строить такой элемент x2, что x1<x2 и между x1 и x2 нет других элементов).

Hаиболее естественным способом упорядочения составных объектов является лексикографический порядок, принятый в любом словаре (сначала сравни­ваются первые буквы слов, потом вторые и т.д.) - именно его мы и будем чаще всего использовать. А вот процедуру получения следующего элемента придется каждый раз изобретать заново. Пока запишем схему перебора в таком виде:

 

x:=First;

While x<>Last Do Next(x);

 

где First - первый элемент; Last - последний элемент; Next - процедура получения следующего элемента.

Hапечатать все последовательности длины N из чисел 1,2,...,M.

First = (1,1,...,1), Last = (M,M,...,M).

 

Всего таких последовательностей будет M^N. Чтобы понять. как должна действовать процедура Next, начнем с примеров.

Пусть N=4, M=3. Тогда:

Next(1,1,1,1) -> (1,1,1,2) Next(1,1,1,3) -> (1,1,2,1) Next(3,1,3,3) -> (3,2,1,1)

Теперь можно написать общую процедуру Next:

 

Procedure Next;

Begin

{ найти i: X[i]<M, X[i+1]=M,..., X[N]=M };

X[i]:=X[i]+1;

X[i+1]:=...:=X[N]:=1

End;

 

Если такого i найти не удается, то следующей последовательности нет - мы добра­лись до последней (M,M,...,M). Заметим также, что если бы членами последова­тельности были числа не от 1 до M, а от 0 до M-1, то переход к следующей означал бы прибавление 1 в M-ичной системе счисления. Полная программа вы­глядит так:

Program Posled;

Const N=4; M=3;

Var x:Array[1..N] Of Byte; i:Byte;

 

Procedure PrintX;

Var i:Byte;

Begin

For i:=1 To N Do Write(X[i]);

Writeln;

End;

 

Function Next:Boolean;

Var i:Byte;

Begin

i:=N;

While (i>0) And (x[ i ] = M) Do Begin

x[ i ]:=1;

Dec(i)

End;

If i>0 Then Begin Inc(x[ i ]); Next:=True; End

Else Next:=False;

End;

Begin

For i:=1 To N Do X[ i ]:=1;

PrintX;

While Next Do PrintX;

End.

Опишем рекурсивную процедуру GPosl(k), генерирующую все последовательности длины N из чисел 1,...,M, у которых фиксировано начало X[1],X[2],...,X[k]. Понятно, что при k=N мы имеем тривиальное решение: есть только одна такая последовательность - это она сама. При k<N будем сводить задачу к k+1:

Procedure GPosl (k:Byte);

Var i, j:Byte;

Begin

If k=N Then PrintX(N)

Else For i:=1 To M Do Begin

X[k+1]:=i;

GPosl(k+1);

End;

End;

Вызов: …. GPosl(0); ….

 

Перестановки

Hапечатать все перестановки чисел 1..N (то есть последовательности длины N, в которые каждое из чисел 1..N входит ровно по одному разу).

First = (1,2,...,N); Last = (N,N-1,...,1).

1 2 3 4 5

1 2 3 5 4

1 2 4 3 5

1 2 4 5 3

1 2 5 3 4

{ для примера} 1 2 5 4 3 -> 1 3 5 4 2 -> 1 3 2 4 5

1 3 2 4 5

1 3 2 5 4

 

Всего таких перестановок будет N!. Для составления алгоритма Next зададимся вопросом: в каком случае i-ый член перестановки можно увеличить, не меняя предыдущих? Ответ: если он меньше какого-либо из следую­щих членов (членов с номерами больше i).

Мы должны найти наибольшее i, при котором это так, т.е. такое i, что X[i]<X[i+1]>...>X[N] (если такого i нет, то перестановка последняя). После этого X[i] нужно увеличить минимально возможным способом, т.е. найти среди X[i+1],...,X[N] наименьшее число, большее его. Поменяв X[i] с ним, остается рас­положить числа с номерами i+1,...,N так, чтобы перестановка была наименьшей, то есть в возрастающем порядке. Это облегчается тем, что они уже расположены в убывающем порядке:

 

Procedure Next;

Begin

{найти i: X[i]<X[i+1]>X[i+2]>...>X[N]};

{найти j: X[j]>X[i]>X[j+1]>...>X[N]};

{обменять X[i] и X[j]};

{X[i+1]>X[i+2]>...>X[N]};

{перевернуть X[i+1],X[i+2],...,X[N]};

End;

 

Теперь можно написать программу:

 

Procedure Next (Var p:boolean);

Var i, j:Byte;

Begin

i:=N-1;

While (i>0) And (X[ i ] > X[i+1]) Do Dec(i); {найти i}

If i>0

Then Begin

j:=i+1;

While (j<N) And (X[ j+1] > X[ i ]) Do Inc(j); {найти j}

Swap(X[ i ],X[ j ]); {обменять X[i] и X[j]};

For j:=i+1 To (N+i) Div 2 Do Swap(X[ j ], X[ N – j + i + 1]); {перевернуть};

p:=True;

E nd

Else p:=False;

End;

 

Begin

For i:=1 to N do X[ i ]:=i;

Repeat

PrintX; Next(p);

Until Not p;

End;

 

Перестановки (рекурсивный алгоритм)

Генератор перестановок. Перестановкой порядка п называется расположение п различ­ных объектов в ряд. Для трех объектов а, b, с имеется шесть пере­становок:

abc, acb, bac, bca, cab, cba. (1)

Задача та же, что в пункте 7.2. Опишем рекурсивную процедуру GPrst(k), предъявляющую все перестановки чисел 1,...,N, у которых фиксировано начало X[1],X[2],...,X[k]. После выхода из процедуры массив X будут иметь то же значение, что перед входом (это существенно!). Понятно, что при k=N мы снова имеем только тривиальное решение - саму перестановку. При k<N будем сводить задачу к k+1:

 

Procedure GPrst (k:byte);

Var i:byte;

Begin

If k=N Then PrintX

Else For i:=k+1 to N do Begin

Swap(x[k+1], x[i]);

GPrst(k+1);

Swap(x[k+1], x[i]);

End;

End;

Begin

For i:=1 to N do X[ i ]:=i;

GPrst(0);

End.

Разбиения

Перечислить все разбиения целого положительного числа N на целые положитель­ные слагаемые (разбиения, отличающиеся лишь порядком слагаемых, считаются за одно).

 

Пример: N=4, разбиения: 1+1+1+1, 2+1+1, 2+2, 3+1, 4.

 

First = (1,1,...,1) - N единиц; Last = (N).

 

Чтобы разбиения не повторялись, договоримся перечислять слагаемые в невозрас­тающем порядке. Для составления алгоритма Next зададимся тем же вопросом: в каком слу­чае i-ый член разбиения можно увеличить, не меняя предыдущих?

Во-первых, должно быть X[i-1]>X[i] или i=1. Во-вторых, i должно быть не послед­ним элементом (увеличение i надо компенсировать уменьшением следующих). Если такого i нет, то данное разбиение последнее. Увеличив i, все следующие эле­менты надо взять минимально возможными, т.е. равными единице:

 

procedure Next;

begin

{найти i: (i<L) and ((X[i-1]>X[i]) or (i=1))}

X[i]:=X[i]+1;

{ L:= i + X[i+1]+...+X[L] - 1 }

X[i+1]:=...:=X[L]:=1

end;

 

Через L мы обозначили количество слагаемых в текущем разбиении (понятно, что 1<=L<=N). Программа будет выглядеть так:

 

1 1 1 1 1

2 1 1 1 {для примера}

2 2 1

3 1 1

3 2

4 1

Function Min(a,b:Integer):Integer; {только для рекурсивной реализации}

Begin If a<b Then Min:=a Else Min:=b; End;

Procedure PrintX(L:Byte);

Var i:Integer;

Begin For i:=1 To L D o write(X[i]); writeln; End;

Procedure Next(Var L:byte);

Var i, j, s:Integer;

Begin

i:=L-1; s:=x[L];

While (i>1) and (x[i-1]<=x[i]) Do Begin s:=s+x[i]; Dec(i); End;

Inc(x[i]);

L:=i+s-1;

For j:=i+1 to L Do x[j]:=1;

End;

Begin

For i:=1 to N do X[i]:=1;

PrintX(N);

L:=N;

Repeat

Next(L);

PrintX(L);

Until L=1;

End.

Рекурсивный вариант генератора разбиений:

Procedure GRzb(s,L:Integer);

Var i: Byte;

Begin

If s = n Then PrintX(L)

Else For i:=1 To Min(x[L], n-s) Do Begin

x[L+1]:=i;

GRzb(s+i,L+1);

End;

End;

Вызов: …. x[0]:=n; GRzb(0,0); ….