Сочетания - Паскаль

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

Сочетанием из n элементов по k называется любое подмножество множества M, со-стоящее из k элементов.

Пример, из множества M = {1, 2, 3, 4, 5} можно составить десять различных сочетаний из 5 по 3:

{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, 
{2, 3, 4}, {2, 3, 5}, {1, 4, 5}, {2, 4, 5}, {3, 4, 5}

Формула для подсчета числа сочетаний следующая: $$C_{n}^{k}=\frac{n!}{k!\left(n-k \right)!}.$$ Если k = 0, тогда $C_{n}^{0}=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

Ясно, что $$C_{5}^{3}=\frac{5!}{3!\left(5-3 \right)!}=\frac{4\cdot 5}{1\cdot 2}=10$$ Но необходима система выборки. Процесс выборки будет таким:

1 2 3 , 1 2 4 , 1 2 5 
1 3 4 , 1 3 5 
1 4 5 
2 3 4, 2 3 5 
2 4 5 
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 элементов - $2^{n}$, (с учетом сочетаний из n по 0 эл-тов), а без учета $2^{n}-1$ Так, для 5 элементов их будет $2^{5}-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.

Пример. Получить все сочетания из n элементов заданного массива a(n).

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

Идея: будем перебирать не сами элементы массива, а их номера.

Program generator_combination; 
{Генератор всех сочетаний}
{для произвольного массива}
const 
 n1=100;
type 
 t=array[1..n1] of integer; 
var 
 a,x,min,max:t; 
 i,n,r:integer; 

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

Procedure gen_comb(a,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(a[x[j]]:4);
 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('Вводите элементы массива'); 
 for i := 1 to n do 
 begin 
 write('Введите ', i, '-й элемент '); readln(a[i]) 
 end; 
 writeln('Всевозможные сочетания из ', n, ' элементов'); 
 for i: 1 to n do gen_comb(a,x,min,max,n,i,r); 
 writeln('Число всех сочетаний равно r = ', r) 
 end.