Закрыть

Комбинаторика. Часть 2

Автор: Васин Алексей
Опубликовано 08.02.2008 в 15:56
Раздел: Дискретная математика

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

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

Перейдем к сочетаниям без повторений. Число (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.

 

Комментарии (0)

Комментировать могут только зарегистрированные пользователи

Подразделы
Новые статьи
Aрхив статей