Продолжаем разговор о генерации комбинаторных объектов. В этой части поговорим о генерации сочетаний.

Сочетания без повторений

Перейдем к сочетаниям без повторений. Число (n,r)-сочетаний без повторений обозначается  С^r_n и равно n!/((n-r)!r!). Наша цель, как и раньше, по номеру сочетания i получить все значения, входящие в сочетание. Перечислим, например, все (4,3)-сочетания без повторений: 123, 124, 134, 234. Таких сочетаний 4 = 4!/(3!1!)=C³₄. Заметим, что на j-ой позиции (j= 1, 2, 3) значение не больше (n-r+j). Для (4,3)-сочетаний без повторений при j=2 (последняя позиция) значение не больше трех, при j=1 – не больше 2. Рассмотрим алгоритм генерирующий все сочетания без повторений.

Программа просматривает все значения на позициях в сочетании, начиная с последней r-ой позиции. Определяется позиция j, значение в которой m[j] меньше (n+j-r). Как видно из примера, такая позиция всегда существует для всех сочетаний без повторений, кроме последнего. Последнее сочетание в данном случае нас не интересует, так как после него нет сочетаний. После нахождения, начиная с конца сочетания, такой позиции j, значение в ней m[j] увеличивается на единицу, а значение в следующей (j+1)-ой позиции будет на единицу больше нового m[j]. Значение в последней r-ой позиции будет на (r-j) больше нового m[j]. Программа sochetanie_bez_pevtorenii осуществляет перечисление всех (n,r)-сочетаний без повторений:

 
	program sochetanie_bez_pevtorenii;
 
	const n=7; r=5;
 
	var i,j,l,c,f:integer; m:array[1..n] of integer;
 
	begin
 
	   c:=r+1;
	   for i:=r+2 to n do c:=c*i;
 
	   f:=1;
           for i:=2 to n-r do f:=f*i;c:=c div f;
 
	   for i:=1 to n do
 
	      begin
 
        	m[i]:=i; if i<=r then write(m[i]:1);
 
	      end;
 
	   write(' '); for i:=2 to c do
 
	      begin
 
	         f:=0;
		 j:=r;
                 repeat
 
	            if m[j]<(n-r+j) then
 
			begin
 
			   m[j]:=m[j]+1; for l:=j+1 to r do
 
                 	   m[l]:=m[j]+l-j; f:=1;
 
               		end;
 
		    j:=j-1;
 
		 until f=1;
                 for j:=1 to r do write(m[j]:1);
                 write(' ');
 
      	      end;
 
	      writeln;
 
	end.

Здесь с – общее число сочетаний, m[1..n] – массив значений на позициях, f – флаг, обозначающий нахождение нужной позиции в сочетании. Эта же задача может быть решена с помощью рекурсивной процедуры nab.

	program sochetanie bez pevtorenii1;
 
	const n=7; r=5;
 
	var i,j,c,f:integer; m:array[1..n] of integer;
 
	
	procedure nab(p:integer);
 
	begin
 
   	  m[p]:=m[p]+1;
	  if m[p]>n-r+p then
 
            begin
 
               f:=p-1;nab(f);
 
            end;
 
	end;
 
 
	begin
 
   	   c:=r+1;
   	   for i:=r+2 to n do c:=c*i;
 
   	   f:=1;
 	   for i:=2 to n-r do f:=f*i;
           c:=c div f;
 
   	   for i:=1 to n do
 
              begin
 
         	 m[i]:=i; if i<=r then write(m[i]:1);
 
      	      end;
 
   	      write(' ');
	   for i:=2 to c do
 
      	      begin
 
		f:=r;
		nab(f);
		for j:=f+1 to r do m[j]:=m[j-1]+1;
 
         	for j:=1 to r do write(m[j]:1);
		write(' ');
 
      	      end;
 
   	   writeln;
 
	end.

Здесь f – номер нужной позиции в сочетании. Алгоритм в программах sochetanie_bez_pevtorenii и sochetanie_bez_pevtorenii1 один и тот же, только реализация разная.

Сочетания с повторениями

Для перечисления всех сочетаний с повторениями воспользуемся формулой: С^r_n+r-1. Для этого n-элементное множество целых чисел увеличим на (r-1) элемент, которые будут принимать значения от (n+1) до (n+r-1). Попадание элемента, равного (n+1), из увеличенного множества в сочетание с повторениями будет означать дублирование элемента, находящегося на первой позиции в сочетании. Попадание элемента, равного (n+j), из увеличенного множества в сочетание с повторениями будет означать дублирование элемента, находящегося на j-ой позиции в сочетании. Если элемент на последней позиции будет равен (n+r-1), то значит в последней r-ой позиции должен быть тот же элемент, что и на предпоследней.

Значение на первой позиции в сочетании не больше (n-r-1)-r+1=n, т.е. элементы дублирования из увеличенного множества на первой позиции никогда не окажутся. На второй позиции может оказаться первый элемент дублирования, равный (n+1). На третьей позиции в сочетании могут оказаться уже два элемента дублирования, равные (n+1) или (n+2). На последней позиции может оказаться любой их элементов дублирования. Если на первой позиции в сочетании число, а на всех остальных позициях элементы дублирования, то сочетание состоит из r одинаковых значений, равных значению на первой позиции в сочетании. Программа sochetanie_s_pevtoreniami осуществляет перечисление всех (n,r)-сочетаний c повторениями:

	program sochetanie_s_pevtoreniami;
 
	const n=7; r=6;
 
	var i,j,l,c,f:integer;
	m:array[1..(n+r-1)] of integer;
 
	mp:array[1..r] of integer;
 
	begin
 
	   c:=r+1;
	   for i:=r+2 to n+r-1 do c:=c*i;
 
	   f:=1;
	   for i:=2 to n-1 do f:=f*i;c:=c div f;
 
	   for i:=1 to n+r-1 do
 
	      begin
 
        	m[i]:=i; if i<=r then write(m[i]:1);
 
	      end;
 
	   write(' ');
	   for i:=2 to c do
 
	      begin
 
	         f:=0;
		 j:=r;
		 repeat
 
	            if m[j]<(n-1+j) then
 
              	      begin
 
                 	m[j]:=m[j]+1; for l:=j+1 to r do
 
                  	m[l]:=m[j]+l-j; f:=1;
 
              	      end;
 
           	    j:=j-1;
 
                until f=1;
		for j:=1 to r do
 
       		   begin
 
              	      mp[j]:=m[j];
 
		      if m[j]>n then mp[j]:=mp[m[j]-n];
		      write(mp[j]:1);
 
                   end;
 
                write(' ');
 
             end;
 
   	     writeln;
 
	  end.