В этой
теме рассматриваются элементы комбинаторики и алгоритмы решения комбинаторных
задач.
3. Размещения. Перестановки.
Сочетания.
Имеется n различных
предметов. Сколько из них можно составить k-расстановок? При этом две расстановки
считаются различными, если они либо отличаются друг от друга хотя бы одним
элементом, либо состоят из одних и тех же элементов, но расположенных в
разном порядке. Такие расстановки называют размещениями без повторений.
Ank =n(n-1)...(n-k+1).Еще эту формулу можно записать следующим образом: Ank =n! / (n-k)!Размещение с повторениями из n элементов множества Е={a1,a2,...,an} по k - всякая конечная последовательность, состоящая из k членов данного множества Е. Два размещения с повторениями считаются различными, если хотя бы на одном месте они имеют различные элементы множества Е. Число различных размещений с повторениями из n по k равно nk. Задача. Напечатать все последовательности длины k из чисел 1..n. Решение: Будем печатать их в лексикографическом порядке (последовательность а предшествует последовательности b, если для некоторого i их начальные отрезки длины i равны, а (i+1)-ый член последовательности а меньше). Первой будет последовательность <1,1,...,1>, последней - <n,n,...,n>. Будем хранить последнюю напечатанную последовательность в массиве x[1],..,x[k]. last[1],..,last[k] положим равным n. Для того, чтобы перейти к следующей последовательности надо: двигаясь с конца последовательности, найти самый правый член, меньший n, увеличить его на 1, а идущие за ним члены положить равными 1. Процедура print(x:massiv) - вывод последовательности.Функция egual(x,last:massiv):boolean - сравнивает элементы массивов, если x<>last, то egual:=false иначе egual:=true. for i:=1 to k do x[i]:=1; Перестановки
из n элементов - частный случай размещения элементов из Е по k, при k=n.
Pn=Ann=n·(n-1)·...·2·1=n!Алгоритм генерации перестановок в лексикографическом порядке: 1. Просматриваем а1,...,аn с конца до тех пор, пока не попадется ai<ai+1. Если таковых нет, то генерация закончена. 2. Рассматриваем ai+1,ai+2,...,an. Найдем первый с конца am больший ai и поменяем их местами. 3. ai+1,ai+2,...,an переставим в порядке возрастания (для этого достаточно её переписать с конца). 4. Печатаем найденную перестановку. 5. Возвращаемся к пункту 1. Первой при этом будет перестановка <1,2,..,n>, последней - <n,..,2,1>. Сочетания
элементов из Е={a1,...,an} по k называется упорядоченное
подмножество из k элементов, принадлежащих Е и отличающиеся друг то друга
составом, но не порядком элементов.
Задача. Перечислить все возрастающие последовательности длины k из чисел 1..n в лексикографическом порядке (все сочетания из n по k). Например: при n=5, k=2 получаем:Решение: Минимальной будет последовательность <1,2,...,k>, а максимальной - <n-k+1,...,n-1,n>. Каждый i-ый член последовательности можно увеличить, если он меньше n-k+i. После увеличения i-го элемента все следующие должны возрастать с шагом 1 function poisk1(x:massiv):boolean;Функции poisk1 и poisk2 организуют поиск i-го элемента, который нужно увеличить на 1 Процедура print печатает полученную последовательность. for j:=1 to m do x[j]:=j; Задача. Перечислить все разбиения целого положительного числа n на целые положительные слагаемые (разбиения, отличающиеся лишь порядком слагаемых, считаются за одно). Например: n=4 разбиения 1+1+1+1, 2+1+1, 2+2, 3+1, 4.Решение: Договоримся, что 1) в разбиениях слагаемые идут в невозрастающем порядке, 2) сами разбиения мы перечисляем в лексикографическом порядке. Разбиение храним в начале массива x[1]..x[n], при этом количество входящих в него чисел обозначим k. В начале x[1]=...=x[n]=1, k=n, в конце x[1]=n,k=1. В каком случае x[i] можно увеличить, не меняя предыдущих?Во-первых, должно быть x[i-1]>x[i] или i=1. Во-вторых, i должно быть не последним элементом (увеличение i надо компенсировать уменьшением следующих). Увеличив i, все следующие элементы надо взять минимально возможными. procedure print(x:massiv;m:integer);Литература 1. Н.Я. Виленкин. Комбинаторика Упражнения. 1. Напечатать все размещения без повторений из чисел 1..n по k. |