Перестановки, сочетания, размещения: вывод всех перестановокПредлагаю вниманию часть главы из моей книги "Delphi и Turbo Pascal на занимательных примерах" с описанием алгоритма и программой для вывода всех перестановок из N элементов. Алгоритм выводит перестановки в таком порядке, который обладает двумя замечательными свойствами. В архиве per.zip вы найдёте текст и исполняемый файл описываемой Delphi-программы, которая легко переводится на Turbo Pascal (уберите первую строку). А сейчас мы рассмотрим другой вариант процедуры вывода всех перестановок в виду того, что он обладает замечательными особенностями. Этот вариант был найден в 1958 г., а рассматриваемый далее алгоритм и программу составил я. Сначала ознакомимся с понятием беспорядка, но не того, при котором на лоток привода CD ROM ставят чашку с кофе, а с математическим беспорядком. Последовательность чисел 1, 2, 3, 4, с математической точки зрения, обладает полным порядком, т. к. все ее элементы упорядочены по возрастанию. Если мы переставим местами числа 2 и 1, то в этой последовательности возникнет один беспорядок, т. к. одно большее число стоит левее меньшего. А если переставить местами числа 1 и 4: 4, 2, 3, 1, как здесь подсчитать число беспорядков? В общем случае, надо для каждого числа подсчитать, сколько чисел, больших него, стоят левее, чем оно. Для двойки это одно число, для тройки тоже одно, а для единицы целых три. Итого, в этой последовательности имеется пять беспорядков. Подсчет числа беспорядков зависит от того, что мы определяем как порядок. Мы могли бы считать порядком размещение чисел от больших к меньшим и для каждого числа суммировать число чисел, меньших его, которые стоят левее его. Вот, собственно, и все о теории беспорядков. Если присмотреться к только что рассмотренному алгоритму получения очередной перестановки, то мы увидим, что в нем неявно присутствовало понятие беспорядка: на шаге 2 мы для числа с i го места увеличиваем на минимум число беспорядков, обменивая m[i] с более правым числом, большим его, и на шаге 3 приводим хвост последовательности в порядок. Это аналогично тому, как наращивается на единицу счетчик с 0999 до 1000: старший разряд увеличивается на единицу, а все разряды, младшие него, сбрасываются в нуль. Вернемся к уже промелькнувшей идее "лесенки" и будем с ее помощью получать перестановки рекуррентно, пока нас не осенит какая нибудь гениальная идея насчет получения очередной перестановки по предыдущей. Начнем с перестановки из одного числа, это просто: 0 Теперь получим из нее все перестановки из двух чисел. Для этого выпишем перестановку 2 раза, оставляя слева место для числа 1: 0 0 и впишем в каждую строку число 1, двигая его лесенкой справа налево: 0 1 1 0 Мы получили все перестановки из двух чисел. Теперь аналогично выпишем их, повторив каждую строку 3 раза, оставляя между числами место для числа 2: 0 1 0 1 0 1 1 0 1 0 1 0 Применяя нашу любимую "лесенку", получаем все перестановки из трех чисел: 0 1 2 0 2 1 2 0 1 2 1 0 1 2 0 1 0 2 Вы еще не заметили общего правила? Тогда повторим этот прием для получения перестановок из четырех чисел, выписав каждую перестановку из трех чисел четыре раза: 0 1 2 3 0 1 3 2 0 3 1 2 3 0 1 2 3 0 2 1 0 3 2 1 0 2 3 1 0 2 1 3 2 0 1 3 2 0 3 1 2 3 0 1 3 2 0 1 3 2 1 0 2 3 1 0 2 1 3 0 2 1 0 3 1 2 0 3 1 2 3 0 1 3 2 0 3 1 2 0 3 1 0 2 1 3 0 2 1 0 3 2 1 0 2 3 Мы видим следующее:
Для нахождения алгоритма получения следующей перестановки по данной надо ответить на вопрос: какие соседние числа на данном шаге следует обменять местами, т. к. мы видим, что у нас постоянно происходит обмен какой то пары соседних чисел. А что если в каждой строке вывести числа беспорядков для всей последовательности, а также для всех более младших последовательностей? В листинге 1.7 за перестановками вы в каждой строке видите числа беспорядков для всей перестановки и для этой перестановки, из которой последовательно вычеркнуты числа 3 и 2. Листинг 1.7. Перестановки с беспорядками 0 1 2 3 0 0 0 0 1 3 2 1 0 0 0 3 1 2 2 0 0 3 0 1 2 3 0 0 3 0 2 1 4 1 0 0 3 2 1 3 1 0 0 2 3 1 2 1 0 0 2 1 3 1 1 0 2 0 1 3 2 2 0 2 0 3 1 3 2 0 2 3 0 1 4 2 0 3 2 0 1 5 2 0 3 2 1 0 6 3 1 2 3 1 0 5 3 1 2 1 3 0 4 3 1 2 1 0 3 3 3 1 1 2 0 3 2 2 1 1 2 3 0 3 2 1 1 3 2 0 4 2 1 3 1 2 0 5 2 1 3 1 0 2 4 1 1 1 3 0 2 3 1 1 1 0 3 2 2 1 1 1 0 2 3 1 1 1 На самом деле, нам первый столбец беспорядков не нужен, он приведен здесь для полноты. Из листинга 1.7 видно, что если в какой-то перестановке число беспорядков без максимального числа 3 (это число беспорядков стоит во втором столбце беспорядков) четно и максимальное число не самое левое, то в следующей перестановке максимальное число меняется местами со своим левым соседом. Если это число беспорядков нечетно и максимальное число не самое правое, то оно меняется местами со своим правым соседом. Остается разобрать случаи, когда тройка является самым левым элементом в перестановке и число беспорядков без нее четно, и когда тройка является самым правым элементом в перестановке и число беспорядков без нее нечетно. В этих случаях обменивается местами со своим соседом какое-то меньшее число. Но ведь это аналогично тому, что мы рассмотрели двумя абзацами выше: в этих случаях мы вычеркиваем тройку и рассматриваем эту перестановку без нее. Старшее число теперь у нас двойка. Если число беспорядков без двойки (это число стоит в третьем столбце беспорядков) четно и двойка не самая левая, то двойка меняется местами со своим левым соседом. Если число беспорядков без двойки нечетно и двойка не самая правая, то она меняется местами со своим правым соседом. Для остальных случаев надо вычеркнуть двойку и рассуждать аналогично. Теперь максимальное число — единица (см. 12 ю строку предыдущего листинга), она стоит справа, и число беспорядков без нее нулевое, т. е. четное. И тут верно открытое нами правило: мы меняем единицу с ее левым соседом нулем. Вот, в общем, и весь алгоритм получения следующей перестановки, составить который нам помогло понятие числа беспорядков. Опишем теперь этот алгоритмего более формально. Как и в случае с программой per1.pas, у нас будет та же функция NextPer, которая будет на входе получать массив m как var параметр, и число n — количество элементов в перестановке. Если NextPer создаст следующую перестановку, то она возвратит TRUE (и конечно, новую перестановку в массиве m), если на входе окажется последняя возможная перестановка, то функция ничего не сделает и возвратит FALSE. Вычеркивать числа мы не будем, а просто заведем две переменные i1 и i2 — индексы начального и конечного числа в текущей перестановке, которую мы рассматриваем. Вначале i1 присвоим 0, а i2 — n–1. Когда нам надо будет вычеркнуть очередное максимальное число, мы увеличим i1 или уменьшим i2 на единицу, ведь число для вычеркивания у нас всегда стоит с краю. Вот сам формальный алгоритм. Задаем начальные границы текущей рассматриваемой части перестановки: i1:=0; i2:=n–1; Задаем максимальный элемент в рассматриваемой перестановке: max:=n–1.
Вы наверно заметили, что этому алгоритму получения следующей перестановки в отличие от предыдущего требуется, чтобы диапазон переставляемых чисел был строго от 0 до n–1. Для работы с другими диапазонами чисел нужно исправлять алгоритм и текст функции NextPer. В таком случае условие основного цикла можно было записать так: вместо i1 >= i2 написать max = 0. Вдумчивый читатель может заметить, что в алгоритме мы один раз переходим на метку 1, где проверяем выполнение условия цикла, а другой раз переходим к пункту 2, где условие i1 >= i2 не проверяется. Не возникнет ли из-за этого ошибка? Можно, конечно, оба раза переходить к метке 1, но ошибка здесь не возникает, потому что мы приходим к равенству границ i1 и i2, только увеличивая i1. Этот момент соответствует последней строке (у нас в примере это 1 0 2 3). Здесь мы увеличиваем i1 на единицу и получаем i1 и i2, равными одному. Текущая перестановка здесь состоит из одного нуля. В листинге 1.8 вы видите полный текст программы с моим алгоритмом получения следующей перестановки. Листинг 1.8. Программа с моим алгоритмом получения перестановок. {$apptype console}
{ Автор Мельников Сергей, www.iqfun.ru }
program Per2;
LABEL EX;
CONST
MAXN=10;
TYPE
tmw=array[0..MAXN-1] of word;
VAR
i,n: word;
m: tmw;
numall: longint;
{ Процедура выдачи в массиве m следующей перестановки чисел
0, 1, 2, ..., n-1 по предыдущей. Начиная с перестановки
0, 1, ..., n-1, можно получить все n! перестановок, причем каждая
следующая будет отличаться от предыдущей ровно одной транспозицией
соседних элементов.
}
function NextPer(var m: tmw; n: word): boolean;
LABEL 1,2;
VAR
i,j,i1,i2,max,numbesp,indmax: word;
begin
{ Зададим начальные границы рассматриваемой перестановки }
i1:=0;
i2:=n-1;
{ Зададим максимальный элемент в рассматриваемой перестановке }
max:=n-1;
while i1 < i2 do
begin
{ Подсчитаем число беспорядков для чисел, меньших max }
1: numbesp:=0;
for i:=i1 to i2-1 do
begin
if m[i] < max then
for j:=i+1 to i2 do
if m[j] < m[i] then Inc(numbesp);
end;
{ Найдем индекс indmax числа max в перестановке m }
for i:=i1 to i2 do
if m[i] = max then
begin
indmax:=i;
goto 2;
end;
2: if Odd(numbesp) then
begin
if indmax <> i2 then
begin
m[indmax]:=m[indmax+1];
m[indmax+1]:=max;
NextPer:=TRUE;
Exit;
end;
{ Переходим к перестановке без max }
Dec(max);
Dec(i2);
goto 1;
end;
if indmax <> i1 then
begin
m[indmax]:=m[indmax-1];
m[indmax-1]:=max;
NextPer:=TRUE;
Exit;
end;
{ Переходим к перестановке без max }
Dec(max);
Inc(i1);
end;
NextPer:=FALSE;
end; {NextPer}
BEGIN
Write('Введите число элементов перестановки: (1-',MAXN,'): ');
{ Получаем число элементов перестановки }
Readln(n);
Writeln;
if (n < 1) or (n > MAXN) then
begin
Writeln('Ошибка ввода.');
goto EX;
end;
for i:=0 to n-1 do m[i]:=i;
numall:=0;
repeat
for i:=0 to n-1 do Write(m[i]:2);
Writeln;
Inc(numall);
until not NextPer(m,n);
Writeln('Всего ',numall);
EX: Writeln('Press Enter to exit...');
Readln;
END.
Взглянув на функцию NextPer, читатель может сказать: а не красивее было бы цикл for i:=i1 to i2 do if m[i] = max then begin indmax:=i; goto 2; end; записать вот так: for indmax:=i1 to i2 do if m[indmax] = max then goto 2; Да, красивее, но этот код при попытке перенести его в другой язык или компилятор может преподнести сюрприз: ведь счетчики циклов некоторые оптимизирующие компиляторы держат в регистрах процессора, поэтому при выходе из цикла значение этого счетчика не определено, т. к. регистры имеют свойство быстро затираться новыми данными. В Turbo Pascal с этим делом все в порядке: оптимизации кода у него нет. И напоследок — два замечательных свойства этого алгоритма генерации перестановок. Во-первых, мы попутно конструктивно доказали интересную теорему о том, что все перестановки из N элементов можно разместить по кругу, и при этом каждая перестановка будет отличаться от своих соседей ровно одной транспозицией соседних элементов. Действительно, взгляните на листинг 1.7: если в последней перестановке поменять местами два первых числа, то мы получим первую перестановку. И во-вторых: строки 13—24 получаются, соответственно, из строк 1—12 путем их реверса, т. е. рассмотрения от конца к началу. Получается, что нам достаточно сгенерировать только первую половину из N! перестановок, а вторая половина получается из первой путем реверса строк! Позже мы получим еще один способ генерации перестановок как побочный результат при составлении другого алгоритма. © IQFun.ru, 2007-2013 гг. |