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

Пусть мы имеем 4 компонента, обозначенные буквами A, B, C, D. Тогда множество всех перестановок из этих компонент будет включать следующие элементы: ABCD, BACD, CABD, DABC, ABDC, BADC, CADB, DACB, ACBD, BCAD, CBAD, DBAC, ACDB, BCDA, CBDA, DBCA, ADBC, BDAC, CDAB, DCAB, ADCB, BDCA, CDBA, DCBA. Приведем алгоритм построения следующей перестановки 9 компонент, обозначенных цифрами от 1 до 9. Первая из таких перестановок - это:

1 2 3 4 5 6 7 8 9.

Пусть текущая перестановка из 9 компонент:

1 9 5 8 4 7 6 3 2.

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

1 9 5 8 6 2 3 4 7.

Как он получается? Прежде всего необходимо просматривать исходный массив от конца к началу, чтобы найти первое число, которое меньше предыдущего; в нашем случае - это 4 (7 < 6 < 3 < 2, а 4 < 7). Далее среди просмотренных чисел справа от найденной четверки мы ищем последнее число, которое больше 4. Это число 6 (7 > 4, 6 > 4, 3 < 4, 2 < 4). Затем меняем эти 2 найденных числа (4 и 6) местами и получаем: 1 9 5 8 6 7 4 3 2.

И теперь числа (справа от 6), которые составляют убывающую последовательность (7 4 3 2), попарно меняем местами так, чтобы они составили возрастающую последовательность (2 3 4 7):

1 9 5 8 6 2 3 4 7.

Это и есть следующая перестановка. А какая перестановка будет последней для данного примера? Надеюсь, что вдумчивый читатель догадался и сам:

9 8 7 6 5 4 3 2 1.

Неформально алгоритм построения очередной перестановки по текущей может быть записан следующим образом:

• От конца к началу перестановки ищем первый элемент B[i] такой, что B[i] < B[i + 1].

• Запоминаем его индекс - I.

• От элемента I + 1 до конца ищем последний элемент, больший, чем B[i], и запоминаем его индекс - K.

• Меняем местами эти элементы с номерами I и K.

• Всю группу элементов от (i + 1)-го элемента до N-го попарно меняем местами: (i + 1)-й элемент с N-м, (i + 2)-й элемент с (N - 1)-м и т. д.

Формализованный алгоритм генерации всех перестановок из N элементов может выглядеть следующим образом:   Ввод N   Прописываем массив B последовательно числами от 1 до N   Это первая - начальная - перестановка, выводим ее   Пока (истина)     i=N     Пока (i>0) и (B[i]>=B[i+1]), i=i-1       Если i=0, то конец работы     Для j от i+1 до N       если B[j]>B[i], то K=j     Обмен значений B[i] и B[k]     Для j от i+1 до (i+ ((N+1-i) div 2))       Обмен значений B[j] и B[N+i+1-j]     Вывод текущей перестановки B Понятно, что цикл парных перестановок «хвоста» массива B нельзя делать от (i + 1)-го до N-го элемента, иначе элементы поменяются местами по два раза и получится, что ничего не изменилось. Цикл нужно выполнить для половины этого «хвоста». Этому и служит несколько сложное для понимания значение конечной переменной цикла: i + (N + 1 - i) div 2. Понятно, что цикл парных перестановок «хвоста» массива B нельзя делать от (i + 1)-го до N-го элемента, иначе элементы поменяются местами по два раза и получится, что ничего не изменилось. Цикл нужно выполнить для половины этого «хвоста». Этому и служит несколько сложное для понимания значение конечной переменной цикла: i + (N + 1 - i) div 2.

Листинг 2.39. Программа, генерирующая перестановки из N компонент const   alphabet : string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'; var   b : array [1..100] of byte;   N,i,j,k : byte;   Procedure SwapB(i,k:byte);     var x : byte;     begin       x:=B[i]; B[i]:=B[k]; B[k]:=x;     end;   Procedure WriteB;     begin       for i:=1 to N do write({alphabet[b[i]]);       writeln;     end; begin   readln(N);   for i:=1 to N do b[i]:=i;   WriteB;   while (true) do     begin       i:=N;       while (i>0) and (B[i]>=B[i+1]) do i:=i-1;       if i=0 then exit;       for j:=i+1 to N do         if (B[j]>B[i]) then K:=j;       SwapB(i,k);       for j:=i+1 to (i+ ((N+1-i) div 2))         do SwapB(j,N+i+1-j);       writeB;     end; end. В программе, генерирующей все перестановки из N компонент, обозначенных за-главными буквами латинского алфавита (листинг 2.39), введены две процедуры: WriteB и SwapB

Процедура WriteB вызывается всякий раз, когда построена очередная перестановка. В данной программе процедура WriteB просто выводит соответствующую по-следовательность

латинских букв. Процедура SwapB(i,k) введена для упрощения понимания главной программы. SwapB просто обменивает значениями два элемента массива B, которые имеют индексы, соответствующие значениям параметров процедуры i и k. Процедура SwapB используется в тексте программы два раза: 1) при обмене значениями двух найденных элементов с индексами I и K; 2) при обеспечении попарного обмена элементов «хвоста», в котором текущий элемент с индексом j обменивается местами со своим «партнером», находящимся на позиции N + i + 1 - j. Таким образом, (I + 1)-й элемент поменяется (при J=I+1) местами с N-м элементом, (I + 2)-й элемент (при J=I + 2) - с (N - 1)-м и т. д. Общее число перестановок из N элементов равно N! (читается - N факториал). Напомним, что N! = 1 * 2 * 3 * ... * N. Сочетания Пусть имеем 5 компонент, обозначенных латинскими буквами A, B, C, D, E. Тогда все сочетания из этих 5 компонент по 3, выписанные в лексикографическом порядке, будут таковы:

• для букв - ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE;

• для цифр - 123, 124, 125, 134, 135, 145, 234, 235, 245, 345.

Неформально алгоритм генерации последовательности чисел в лексикографиче-ском порядке можно записать следующим образом: выберем наименьшие M из имеющихся N чисел и выпишем их в порядке возрастания (в нашем примере - 1 2 3), - это будет начальным сочетанием. Очевидно, что наибольшие M чисел из имеющихся (3 4 5), выписанные в порядке возрастания, составят последнее сочетание. Для того чтобы по текущему сочетанию получать следующее, можно поступать таким образом: находим позицию в текущем сочетании, на которой не стоит по-следнее из возможных значений, и затем увеличиваем его на 1. А все последу-ющие элементы сочетания получаем увеличением на 1 предыдущего элемента сочетания. Например, пусть текущее сочетание таково:

1 3 5.

Анализ начинаем с последней позиции сочетания. 5 - это последнее возможное значение, потому переходим к предыдущей позиции. 3 - это не последнее возможное значение для этой позиции (каковым является 4 в данном случае). Поэтому мы его увеличиваем на 1 и получаем 4. Число в следующей позиции получаем прибавлением 1 к этой 4 и получаем 5. Таким образом следующее сочетание будет:

1 4 5.

Более строго этот алгоритм может быть записан следующим образом:   Ввод N, M (из сколька, по сколько)

  Заносим в массив B числа от 1 до M   Это первое сочетание, выводим его   Пока (истина)     i=M     Пока (i>0) и (b[i]=N-m+i), i=i-1     Если i=0, то работа завершена     B[i]=B[i]+1     Для j от i+1 до M B[j]=B[j-1]+1;     Вывод B - следующей перестановки Листинг 2.40. Программа, выводящая в лексикографическом порядке                              все сочетания из N латинских букв по M uses crt; const   alphabet : string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'; var   b : array [1..100] of byte;   N,M,i,j,k : byte;   Procedure WriteB;     begin       for i:=1 to M do write(alphabet[b[i]]);       writeln;     end; begin   readln(N,M);   for i:=1 to M do b[i]:=i;   WriteB;   while (true) do     begin       i:=M;       while (i>0) and (b[i]=N-m+i) do Dec(i);       if i=0 then exit;       Inc(B[i]);       for j:=i+1 to M do B[j]:=B[j-1]+1;       WriteB;     end; end. Напомним, что общее число сочетаний из N элементов по M может быть вычислено по формуле: