глубину. Процедура поиска с возвращением для нахождения всех решений формально представлена в алгоритме 4.1.

Алгоритм 4.1. Общий алгоритм поиска с возвращениями

Sy =Ау, {Выделитькандидатов] к= 1; {Длиш частичного решения) while к>0 do begin while Sk * 0 do begin

ak £ Sk, {Расширшт частичное решение } Sk = Sk- {ak}; {Удалитьвыбранного кандидата} if{aha2,..., ak) - решение then Сохранить решение; k = k+ 1; {Расшири ть частичное решение) с

end;

k = k- 1: {Вернуться, уменьшить частичное решение) end.

Поиск с возвращением приводит к алгоритмам экспоненциальной сложности, так как из предположения, что все решения

имеют длину не более , исследованию подлежат приблизительно п

Y]Ak\ элементов. В предположении, что все .i \ = констан-

п

ты, получаем экспоненциальную сложность = С . Нужно

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

4.2. Перестановки различных элементов

Перестановки множества различных элементов

относятся к часто порождаемым комбинаторным объектам. Без ограничения общности можно полагать, что элементами множества являются целые числа от 1 до п, т.е. рассматриваются перестановки целых чисел 1, п.

Порождение перестановок на основе метода поиска с возвращениями выполняется в алгоритме 4.2. Заметим, что в процессе приспосабливания общего алгоритма 4.1 поиска с возвращениями к задаче порождения перестановок мы не вычисляли и не хранили явно множества о,. В этом случае легче и достаточно хранить только наименьшее значение из т.е. и следующее значение вычислять по мере необходимости. Проверка условия Sk -р 0 соответствует условию sk< /;, поскольку алгоритм устроен так, что перебор значений элемента выполняется в порядке их возрастания. Поэтому неравенство > п соответствует пустому множеству кандидатов = 0.

Алгоритм 4.2. Порождение перестановок методом поиска с возвращением

= 1; {Первыйкандидат} k = 1; {ДлиHi частичного решения) whilek>0 do begin whilesk<ndo begin

ak = sk; {Расшир итъ частичное решение } sk=sk+l; {Удалитьвыбранного кандидата) while sk<n and not flag(sk)do sk=sk+ 1; ifk=n then Перестановка (%, a2,..., a ) - решение; else begin

k = k + i, {Расширит! частичное решение)

** = i;

while andnetfiagis, do =sk+\;

end; end;

k = k - 1; {Вернут ься, уменьшить частичное решение)

end;

Function flag(sk) {Slouch элемента ske перестановке (aaj,--, а^-О) flag= TRUE;

/ = 1;

while i < k andflag do begin

ifa, = sk then flag = FALSE;

i= i+ 1; end.

Программа на языке Pascal реализации рассмотренного метода генерации перестановок приводится в алгоритме 4.3. Следует отметить, что в программе размерность (длина) и перестановок читается из файла и порождаемые перестановки также сохраняются в файле. Попутно программа вычисляет время порождения всех перестановок с точностью до сотых долей секунды, которое сохраняется в конце файла сгенерированных перестановок.

Алгоритм 4.3. Программа на Pascal е порождения перестановок методом поиска с возвращением

Program Start Bac:kTrack; {Порождение перестановок} uses CRT,DOS; Const max n=20;

Type Vector=array[l..max n] of Longing-Function Flag(Var a:Vector; sk:LongInt;

k:Integer): Boolean;

( Поиск элемента sk в перестановке a[l],a[2],...,a[k-ll } Var i :Integer;

yes :Boolean; begin;

yes:=TP,UE; i:=l; while (i<k) and yes do begin if a[i]=sk then yes:=FALSE; i:=i+l; end;

Flag:=yes; end;{Flag)

Procedure BackTrack (var f-.Text; Var aiVector; n: Integer) ;

{ Генерация перестановок a[1],a[2]a[n] } Const m :LongInt=0; {Количество перестановок) Var s :Vector; i,k :Integer;

begin;

for i:=l to n do [1] И)п s[l]:=l; k:=l;

while k>0 do begin

while s[k]<=n do begin a[k]:=s[k];

repeat {Поиск следующего кандидата на место а [к.! ( s[к]:=s[к]+1;

until or

if k=n then begin {Перестановка найдена) т:=т+1;

Write(f,m,) );

for i:=l to n do Write(f,a[iJ, ); WriteLn (f);

else begin{Поиск первого кандидата на место а[к+1П k:=k+l; s[k]:=1;

while (s[k]<=n) and Not Flag (a, s [k] , k) do s[k]:=s[k]+l;

end;

end; k:=k-l; end;

end;{BackTrack} Var {Main}

f .-Text; (Текстовый файл)

Hour,Minute,Second,SeclOO,rHour,rMinute,rSecond,

rSeclOO :Word; delta :LongInt; begin(Main)

Assignif,BkTrack.in) Reset if) ; {Ф<шл открыт для чтения? Readl.n (f, n) ; {Ввод длины перестановки) Close(f);

Assign(f,BkTrack.out);

открыт для GetTime(Hour,Minute,Second,SeclOO); BackTrack (f,a,r.);

GetTime(rHour,rMinute,rSecond, rSeclOO);

delta:=rHour-Hour; delta:=delta* 60 + rMinute-Minute;

delta:=delta* 60+rSecond-Second;

delta:=delta*100+rSecl00-SeclOO;

WritfeLn(f,Время счета=,delta div 100,.,

delta mod 100, сек'); Close(f); end{Main}.

4.3. Эффективное порождение перестановок

Последовательность я! перестановок на множестве {1, 2;..., }, в которой соседние перестановки различаются так мало, как только возможно, - лучшее, на что можно надеяться с точки зрения мини-

мизации объема работы, необходимого для порождения перестановок. Для того чтобы такое различие было минимально возможным, любая перестановка в нашей последовательности должна отличаться от предшествующей ей транспозицией двух соседних элементов. Такую последовательность перестановок легко построить рекурсивно. Для = 1 единственная перестановка {1} удовлетворяет нашим требованиям. мы имеем последовательность перестановоктг), л2, я3,.. на множестве {I, 2,..., п) в которой последовательные перестановки различаются только транспозицией смежных элементов. Расширим каждую из этих (и - 1)! перестановок, вставляя элемент п на каждое из я возможных мест. Порядок порождаемых таким образом перестановок будет следующим:

(1234

1243

132JJ

1423

[4123

Г4132

.1432 1342

[1324

(3124 J3142

3412

[4312

(4321 3213421 4 3241

[3214

2314 , 12341

2431

[4231 (4213

21312143 [2134

Данную последовательность перестановок можно порождать итеративно, получая каждую перестановку из предшествующей ей и небольшого количества добавочной информации. Этодела-ется с помощью трех векторов: текущей перестановки я = л2,..., я ), обратной к ней перестановкир = (Pi,p2,-,P ) и записи направления в котором сдвигается каждый элемент / (-1, если он сдвигается влево; если вправо; и 0, если не сдвигается).

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

Корректность алгоритма доказывается индукцией по п. Алгоритм порождения всех л! перестановок линеен, сложность его определяется как л! + о{п\). Алгоритм 4.4 - один из наиболее эффективных алгоритмов для порождения перестановок.

Рабочая программа на языке Pascal реализации эффективного метода генерации перестановок приводится в алгоритме 4.5.

В качестве примера в алгоритме 4.6 приводится программа реализации эффективного метода генерации перестановок, написанная на языке Си.

Алгоритм 4.4. Метод эффективного порождения перестановок fori= 1 tondolj z* <А=0;

т0 = = т = n + 1; {Меткиграницы)

Print л =Crcj,5T2,...,7tn); т -гк

while т *\do*\ while я- . л >mdo\rm

р, ~ш [т =т-1

р. - />, ; {Изменить р=п ,nPtr tdrr -т)

Аиоритм 4.5. Программа на Pascalе порождения перестановок эффективным методом

Program Start Effect; (Эффективная генерация

перестановок}

uses CRT,DOS;

Const max n=20; { n<=max n }

Type Vector=array [0. .max n+l] of Integer;

Var f :Text;

{ Генерация перестановок z[l], z[2], .../ z[n] }

Procedure Var z:Vector; n:Integer );

Const k :LongInt=0; {Количество перестановок}

p,d :Vector;

pm,dm,zpm :Integer; i,m,w :Integer;

begin;

for i:=l to n do begin z[i]:=i; p[i]:=i; d{i]:=-l; end; d[l]:=0; m:=n+l;

z [0 J ?- [n+1] :-mi

while mol do begin

{ Печать перестановки } k:=k+l; Write(f,k,) ) ;

for i:=l to n do Write{f,z[i}, V; WriteLn(f); m: =n;

while z[p[m]+d[m] ]>m do begin

d[m] :=-d[m] ; m:=m-l; end; pm:=p[m]; dm:=pm+d[m]; w:=z[pm]; z [pm] : =z [dm] ; z[dm]:=w;

zpm:=z[pm]; w:=p[zpm]; p[zpm]:=pm; p[m]:=w; end; end;{Effect} Var {Main}

n :Integer; {Длина перестановки} Hour,Minute,Second,SeclOO :Word; rHour,rMinute,rSecond,rSeclOO :Word; delta -.Lonqlnt; begin

Assign(f,Effect.in); Reset(f); {Файх открыт для чтения} RoadLn(f,n); {Чтение длины перестановки} Close (f);

Assign(f,Effect.out);

открыт для GetTime(Hour,Minute,Second,SeclOO) ; Effect(z,n);

GetTime(rHour,rMinute,rSecond,rSeclOO);

delta:=rHour-Hour;

delta:=delta*60+rMinute-Minute;

delta:=delta* 60 + rSecond-Second;

delta:=delta*10O+rSecl0O-SeclO0;

WriteLn(f,Время счета=,delta div 100,.,

delta mod 100, сек'); Close(f); end.

Алгоритм 4.6. Программа на Си порождения перестановок эффективным методом

#include <stdio.h>

ttinclude<stdlib.h> #include <time.h> #include <dos.h>

void main ( ) { Генерация перестановок z[l], z[2], z[n]

int n;

int *z,*p,*d;

FILE *f;

struct dostima t t,tnew;

long delta; unsigned long k; int pm, dm, zpm; int i,m, w;

dos gettime (&t);

f=fopen( primer.in , rt ); fscanf(f, %d ,&n) ; z=(int*)malloc( (n+2)*sizeof(int)) ; Перестановка p=(int*)malloc( (n+2)*sizeof(int)) ; Обратная d= (int*)malloc( (n+2)*sizeof(int)) ; Смещение fclose(f) ;

f=fopen ( primer .out , wt ) ;

for( i=i; i<-n; i++ ){ z (i]=p[i]-i; ..Mil- \; ; d[l]=0; z[0]=z[n+l]=m=n+l; k=0; while ( m!=l ) {

Печать перестановки

k++; fprintf(f, \n%ld) ,k);

for( i-1; i<=n; i++ ) fprintf (f, %d ,z [i]) ;

m=n;

while ( z[p[m]+d[m] ]>m ){ d [m] =-d [m] ; m-; )

pm=p [m] ; dm=pm+d[m]; w=z[pm]; z[pm]=z[dm]; z[dm]=w;

zpm=z[pm]; w=p[zpm]; p[zpm]=pm; p[m]=w;

free(z); free(p); free(d);

dos gettime (Stnew);

delta=tnew.hour; delta-=t .hour; delta*=60;

delta+=tnew.minute; delta-=t.minute; delta*=60; delta+=tnew.second; delta-=t.second; delta*=100; delta+=tnew.hsecond; delta-=t.hsecond; fprintf(f, ХпВремя счета %ld.%ld сек ,

(long) (delta/100), (long) (delta%100)); fclose(f);

4.4. Порождение подмножеств множества

Порождение подмножеств множества {аьа2,..., ан} эквивалентно порождению /(-разрядных двоичных наборов ah принадлежащих подмножеству, если и только если /- й разряд равен единице. Таким образом, задача порождения всех подмножеств множества сводится к задаче порождения всех возможных двоичных последовательностей длины п. Очевидно, что наиболее прямым способом порождения всех двоичных наборов длины п является счет в системе счисления с основанием 2, как показано в алгоритме 4.7.

Перевод этого алгоритма на язык подмножеств множества {а а- ..., ап) осуществляется согласно алгоритму 4.8, где добавлен фиктивный элемент апЛ.

Алгоритм 4,7. Счет в системе счисления с основанием 2 для порождения всех п-разрядных наборов

for i= О ton do b = 0;

i=0;

while 1 do

whileb. =\do\bi °\ bt =1

Алгоритм 4.8. Порождение подмножеств счетом в двоичной системе счисления

while апЛ eS do

Print(S), =0;

while a, eSdo \, . ~

[1=1+1

4.4. Порождение подмножеств множества.

Задача Счастливый билет . Дано п (п>2) произвольных цифр: аь а2,..., ап, где а, е {1, 2,..., 9}, и произвольное целое число т. Написать программу, которая расставляла бы между каждой парой цифр аь а2,..., ап, записанных именно в таком порядке, знаки +,- так, чтобы значением получившегося выражения было число т. Например, если аи а2,..., ап соответственно 1,

2,..., 9 и т = 5, то подойдет следующая расстановка знаков: 1-2+3-4+5-6+7-8+9. Если требуемая расстановка невозможна, то сообщить об этом.

Исходные данные вводятся из текстового файла, имеющего следующую структуру:

Первая строка - целое число п.

Вторая строка - целое число т.

Третья строка - цифры аь а2,..., ап через пробелы.

Результаты расчетов сохранить в текстовом файле.

Пример файла исходных данных:

14 71

65884752345789

Пример файла выходных данных:

6+5+8+8+4+7+5+2+3+4-5+7+8+9 = 71

6+5+8+8+4+7+5-2-3+4+5+7+8+9 = 71

6+5+8+8+4+7-5+2+3+4+5+7+8+9 = 71

6-5+8+8+4+7+5+2+3+4+5+7+8+9 = 71

Время счета = 0.60 с.

Ясно, что для решения данной задачи достаточно выполнить полный перебор всех возможных вариантов расстановки знаков ± между каждой парой цифр а{, а2,..., ап и выбрать те расстановки знаков ± , которые удовлетворяют условию равенства суммы величине т. Всего позиций для расстановки + равно п - 1, а значит для полного перебора необходимо проверить 2 1двоич-ных наборов, если будет соответствовать 1, а - 0.

Программа решения задачи счастливый билет представлена алгоритмом 4.9. Процедура SubSet (подмножество) этой программы реализует рассмотренный выше алгоритм 4.7 счета в системе счисления с основанием 2 для порождения всех (п - 1)-разрядных наборов. Порожденные двоичные наборы используются в процедуре Summa (сумма) для формирования суммы, соответствующей данному набору знаков где соответствует 1, а - 0.