Перестановки, сочетания, размещения: вывод всех перестановок

Предлагаю вниманию часть главы из моей книги "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. Чем больше число, тем чаще оно двигается.
  2. Каждое число кроме единицы двигается по лесенке справа налево и обратно среди чисел, меньших его. При этом для чисел, меньших N (здесь у нас N = 3), каждая строка повторяется в зависимости от величины этого числа.
  3. Когда число N доходит до левого или правого края, в следующей строке оно остается там же, т. к. в этой строке двигается какое-то число, меньшее его. Это с уточнением из предыдущего пункта верно и для чисел, меньших N.

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

А что если в каждой строке вывести числа беспорядков для всей последовательности, а также для всех более младших последовательностей? В листинге 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.

  1. Начало основного цикла. Если i1 >= i2, то переходим за цикл к пункту 3.
  2. Рассматривая часть перестановки с индекса i1 до индекса i2 включительно, подсчитаем в numbesp число беспорядков для чисел, меньших max. Найдем индекс indmax числа max в этой же части перестановки от индекса i1 до i2. Если число беспорядков numbesp нечетно, то обмениваем число max с его правым соседом и выходим, возвратив TRUE. Переходим к перестановке без max: уменьшаем max и i2 на единицу и переходим к пункту (метке) 2. Если indmax не равен i1, то обмениваем число max с его левым соседом и выходим, возвращая TRUE. Переходим к перестановке без max, уменьшив max на единицу, увеличив i1 на единицу и совершив переход к пункту (метке) 1. Конец основного цикла.
  3. Выходим, возвращая FALSE.

Вы наверно заметили, что этому алгоритму получения следующей перестановки в отличие от предыдущего требуется, чтобы диапазон переставляемых чисел был строго от 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! перестановок, а вторая половина получается из первой путем реверса строк!

Позже мы получим еще один способ генерации перестановок как побочный результат при составлении другого алгоритма.

© Сергей Мельников, 2007-2013 гг.

Новости игр и головоломок

Пройдите лабиринты на флеш

24.09.2016 Лабиринты разных размеров.

Слова, слова, слова...

09.09.2016 Словесно-интеллектуальный конкурс № 73.

Вот тебе бог, а вот тебе и пророк!

02.09.2016 Литературная викторина № 72.

Новые стихи-каламбуры.

07.07.2016 Не хуже "королей рифмы".

Слова, в словах:

07.07.2016 добавлены слова, разбивающиеся на слова.

Добавлены загадки с метаграммами.

05.07.2016 Шарадные загадки и пародии на них.

Слова, в словах:

04.07.2016 примеры, список слов, в которых прячутся другие слова.

Пополнение вопросов ребром, а также

30.06.2016 вопросы учёного, возникшие утром 1-го января.

Статья о метаграммах.

17.06.2016 Метаграмма - примеры, список метаграмм и добавлялок-вставлялок.

Бессистемное программирование.

09.04.2016 Пример программы для ассемблера FASM.