Сочетания - Паскаль
Существуют задачи, решение которых требует просмотра (перебора) всех элементов массива или, по крайней мере, большей его части. К такого типа задачам относятся задачи, связанные с получением различных сочетаний элементов данного массива.
Сочетанием из n элементов по k называется любое подмножество множества M, со-стоящее из k элементов.
Пример, из множества M = {1, 2, 3, 4, 5} можно составить десять различных сочетаний из 5 по 3:
Формула для подсчета числа сочетаний следующая:
$$C_{n}^{k}=\frac{n!}{k!\left(n-k \right)!}.$$
Если k = 0, тогда \(C_{n}^{0}=1\).
Программными средствами подсчитать число сочетаний можно, используя процедуру:
Пример. Составить программу выборки всевозможных различных трех элементов из мас-сива, состоящего из 5 элементов.
Для простоты рассуждений зададим массив из пяти последовательных натуральных чисел:
Реализуем этот процесс программными средствами.
Во-первых, обратим внимание на последние элементы в полученных сочетаниях, это 5, 4 и 3. Назовем эти элементы - верхними границами подмножеств и обозначим max[1], max[2] и max[3].
Во-вторых, надо ввести и нижние границы подмножеств, значения которых, как видно из построения подмножеств будут равны (начиная с последней границы):
Программа. Генерация сочетаний.
Число всевозможных сочетаний из 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.
Программа. Генератор всех сочетаний.
В предыдущих примерах перебирались натуральные числа, то теперь задача усложнена - массив может состоять из любых чисел (и не только целых).
Идея: будем перебирать не сами элементы массива, а их номера.
Сочетанием из 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}
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.
