Продолжаем разговор о генерации комбинаторных объектов. В этой части поговорим о генерации сочетаний.
Сочетания без повторений
Перейдем к сочетаниям без повторений. Число (n,r)-сочетаний без повторений обозначается Сrn и равно n!/((n-r)!r!). Наша цель, как и раньше, по номеру сочетания i получить все значения, входящие в сочетание. Перечислим, например, все (4,3)-сочетания без повторений: 123, 124, 134, 234. Таких сочетаний 4 = 4!/(3!1!)=C34. Заметим, что на 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 p 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
:=m
+1; if m
>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 p 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 один и тот же, только реализация разная.
Сочетания с повторениями
Для перечисления всех сочетаний с повторениями воспользуемся формулой: Сrn+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 p 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.
