Введение

Комбинаторика осуществляет пересчет и перечисление тех элементов в конечных множествах, которые обладают некоторыми заранее заданными свойствами. Разницу между пересчетом и перечислением можно увидеть из следующего примера. Пересчитать все города в стране с населением более одного миллиона – это значит назвать цифру, а перечислить такие города – это огласить список городов. Алгоритмы комбинаторики легко позволяют решить задачи перечисления элементов множества. Некоторые из задач перечисления решаются без ЭВМ с помощью производящей функции (энумератора), но далеко не все. Кроме того, использование производящей функции занимает гораздо больше времени, чем составление алгоритмов, написание и отладка программ. При необходимости и задачи пересчета могут быть решены с помощью алгоритмов комбинаторики, хотя большинство задач пересчета решается без ЭВМ. Надо только не забывать, что алгоритмы дают ответ в числах для каждого конкретного примера пересчета, а теория дает ответ в формулах, объединяющих группу примеров пересчета.

По собственному опыту знаю, что при решении некоторых приходится реализовывать перечисление тех или иных обектов.

Определение. (n,r)-выборки - выборки r элементов из n-элементного множества.

Определение. Упорядоченная (n,r)-выборка называется размещением из n по r, неупорядоченная – сочетанием из n по r. Естественно, что при одних и тех же из n и r размещений больше, чем сочетаний. Кроме того, (n,r)-выборки могут быть с повторениями элементов в них, и без повторений.

Размещения с повторениями

Число (n,r)-раэмещений с повторениями обозначается А_n^r  и равно n^r. 

Программа razm осуществляет перечисление всех размещений с повторениями:

	
program razm;
	const n=5; r=3;
	var i,j,k,a:integer; 
	begin
	   a:=n;
	   for i:=2 to r do a:=a*i;
	   for i:=1 to a do
	      begin
	         k:=i-1; 
	         for j:=1 to r do
	            begin
	               write((k mod n)+1); k:=k div n;
	            end;
	         write(' ');
 	      end;
	   writeln;
	end

Здесь переменная a равна числу размещений с повторениями . В данном случае выборка производится из множества, состоящего из n целых чисел от единицы до n.

Размещение без повторений

Рассмотрим теперь размещения без повторений элементов множества в них. Число (n,r)-размещений равно n!/(n-r)!. Здесь r строго не больше n, тогда как в размещениях с повторениями n и r любые целые числа. Программа razmbp осуществляет перечисление всех (n,r)-размещений без повторений:

	
program razmbp;
	const n=5; r=3;
	var i,j,k,l,a,f:integer; m:array[1..n] of integer;
	begin
	   a:=1;
	   for i:=n-r+1 to n do a:=a*i;
	   for i:=1 to a do
	      begin
	         k:=i-1; for j:=1 to n do m[j]:=j;
	         for j:=1 to r do
	            begin
	               l:=k mod (n-j+1)+1; k:=k div (n-j+1);
	               write(m[l]:1); for f:=l to n-j do m[f]:=m[f+1];
	            end;
	         write(' ');
	      end;
	   writeln;
	end.

     Здесь a - общее число размещений. По номеру размещения i осуществляется вывод самого размещения. M[1..n] – вспомогательный массив для того, чтобы значения на позициях в размещении не повторялись. Программа razm основана на формуле n!/(n-r)!, также как программа razm основана на формуле nr. Здесь в цикле по j от 1 до r число l меняется от 1 до (n-j+1), а программе razm это изменение не зависило бы от j, l менялось бы от 1 до n. Чтобы избежать повторений значений на позициях в размещении, на каждом следующем шаге по j от 2 до r получение значений на позициях осуществляется из числа элементов множества, которое на единицу меньше числа элементов для получения значений на предыдущем шаге. На первом шаге в первой позиции значения получаются из всего n-элементного множества, на втором – из (n-1) элементов, … , на r-м шаге – из (n-r+1) элементов множества. После присвоения значению j-ой позиции l-го элемента множества, все элементы множества, начиная с (l+1)-го и кончая (n-j)-м, сдвигаются на один элемент вперед. M[l]=m[l+1], … , m[n-j]=m[n-j+1]. (n-j)-ый элемент будет последним при определении значения следующей (j+1)-й позиции. Таким образом, l-ый элемент множества уничтожается, при определении значений следующей позиции он рассматриваться не будет. Такой сдвиг с затиранием значений элементов множества увеличивает время работы программы.

      Далее программу razm можно усложнять под любые корректные условия на элементы множества. Условия равенства суммы значений на позициях в размещениях без повторений могут быть корректными, а условия наличия всех n элементов в размещениях без повторений при r меньше n – нет.