Сочетание

СОЧЕТАНИЯ

Сочетания в математике

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

Сочетаниями из n различных элементов по m называются соединения (наборы), каждое(ый) из которых содержит m элементов из n. Сочетания из n различных элементов по m отличаются друг от друга только элементами. Порядок следования элементов не учитывается.

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

Сочетания из n по m элементов с повторениями называются соединения, содержащие m элементов, причем любой элемент может входить в соединение некоторое число раз, не большее m.

Вывод формулы:

Для нахождения формулы закодируем каждое сочетание с повторениями с помощью нулей и единиц. Сначала напишем столько единиц, сколько взято элементов первого типа. Потом, чтобы отделить элементы первого типа от второго, запишем нуль (если не было ни одного элемента первого типа и второго типа, то в записи появятся два следующих друг за другом нуля). Затем напишем столько единиц, сколько взято элементов третьего типа, снова напишем нуль и т. д., пока не будет выписаны единицы, различных сочетаний из n элементов по m с повторениями равно числу перестановок с повторениями, которые можно составить из m единиц и n - 1 нуля.

                           Сочетания в информатике

Procedure combination(n,k:integer; var s:longint);

var

 i:longint;

begin

 s:=1;

 if k=0 then s:=1

 else for i:=1 to n-k do s:=s*(k+i) div i

end;

Одно дело - подсчет числа сочетаний, совершенно другое - получить заданные сочетания, т.е. выбрать указанное количество элементов из заданного массива или множества. 

Пример. Составить программу выборки всевозможных различных трех элементов из массива, состоящего из 5 элементов. 

Для простоты рассуждений зададим массив из пяти последовательных натуральных чисел:

1 2 3 4 5

Реализуем этот процесс программными средствами. 

Во-первых, обратим внимание на последние элементы в полученных сочетаниях, это 5, 4 и 3. Назовем эти элементы - верхними границами подмножеств и обозначим max[1], max[2] и max[3]. 

Во-вторых, надо ввести и нижние границы подмножеств, значения которых, как видно из построения подмножеств будут равны (начиная с последней границы):

min[1]=3, min[2]=2, min[3]=1.

Программа. Генерация сочетаний.

Program Generator_combination;

{Генератор сочетаний}

const

 n=5; k=3; n1=100;

type

 t=array[1..n1] of integer;

var

 x,min,max : t;

 i,j,r:integer;

begin // задаются начальные значения max,min,x

for j:=1 to k do

 begin

 max[j]:=n-j+1;

 min[j]:=k-j+1;

 x[j]:=min[j]

 end;

writeln('Сочетания из ',n,' эл-тов по ', k, ' элементов');

while i<=k do

 begin

 for j:=k downto 1 do write(x[j], ' '); writeln;

 r:=r+1; i:=1;

 while (i<=k) and (x[i]=max[i]) do i:=i+1;

 if i<=k then x[i]:=x[i]+1;

 for j:=i-1 downto 1 do

 begin

 min[j]:= x[j+1]+1;

 x[j]:=min[j]

 end

 end;

writeln('Общее число сочетаний равно r = ', r)

end.

Пример. Генерация всех возможных сочетаний из n элементов. 

Число всевозможных сочетаний из n элементов - 2n, (с учетом сочетаний из n по 0 эл-тов), а без учета 2n−1 Так, для 5 элементов их будет 25−1=31. 

В основной программе организуем цикл от 1 до n и в качестве входного параметра для количества выбираемых элементов k будем вводить значение параметра цикла. 

Процедура gen_comb: входные параметры - массивы чисел (x: t), массивы нижних и верхних границ (min, max:t), хотя можно обойтись и без указания массивов в качестве входных параметров, но общее число элементов массива n и количество выбираемых элементов - k вводить надо обязательно. Выходной параметр - число всех сочетаний r. 

Программа. Генератор всех сочетаний.

Program generator_combination;

{Генератор всех сочетаний}

const

 n1=100;

type

 t=array[1..n1] of integer;

var

 x,min,max:t;

 i,n,r:integer;

Procedure gen_comb(x,min,max:t; n,k:integer; var r:integer);

var

 i,j:integer;

begin

 for j:=1 to k do

 begin

 max[j]:=n-j+1;

 min[j]:=k-j+1;

 x[j]:=min[j]

 end;

 i:=0;

 while i<=k do

 begin

 for j:=k downto 1 do write(x[j]:8);

 writeln;

 r:=r+1; i:=1;

 while (i<=k) and (x[i]=max[i]) do i:=i+1;

 if i<=k then x[i]:=x[i]+1;

 for j:=i-1 downto 1 do

 begin

 min[j]:=x[j+1]+1; x[j]:=min[j]

 end

 end

end;

{--------------------------------------------}

begin

 write('Введите число элементов массива n = '); readln(n);

 writeln('Всевозможные сочетания из ', n, ' элементов');

 for i := 1 to n do gen_comb(x, min, max, n, i, r);

 writeln('Число всех сочетаний равно r = ', r)

 end.