Размещения из n элементов - Паскаль
Размещения относятся к комбинаторике. В программировании при решении переборных задач приходится не только подсчитывать число размещений, но и получать сами эти размещения. Здесь рассмотрено несколько задач на эту тему.
Определение. Размещением из n элементов по k называется всякое упорядоченное подмножество данного множества, содержащее k элементов.
Например, из множества M = {1,2,3,4} можно образовать 12 различных размещений, из 4 по 2:
Число размещений, взятых из n элементов по k, мы будем обозначать символом , оно оп-ределяется по формуле:
$$A_{n}^{k}=\frac{n!}{\left(n-k \right)!}$$
Значит,
$$A_{4}^{2}=\frac{4!}{2!}=3\cdot 4=12$$
Вычислить число размещений можно и по другой формуле:
$$A_{n}^{k}=n\cdot \left(n-1 \right)\cdot \left(n-2 \right)\cdot ...\cdot \left(n-k+1 \right)$$
Замечание. Составив процедуру вычисления размещений по этому принципу мы избегаем недопустимо больших чисел, которые могут образовываться при вычисление факториалов и упрощаем составление программ, а также имеем возможность в дальнейшем применять процедуру размещений в других программах. Поэтому эта формула подходит лучше для решения задачи.
Программа. Число размещений из n элементов по k элементов.
Таким образом, нужно использовать не только процедуру вырабатывающую сочетания, но и процедуру перестановок из этих сочетаний. Комбинация этих процедур дает необходимый результат. На основе этих рассуждений составим программу решения следующего примера.
Пример. Составить программу вывода на экран размещений из n элементов по k элементов. Заданным массивом являются натуральные числа от 1 до n.
Программа. Генератор размещений
Определение. Размещением из n элементов по k называется всякое упорядоченное подмножество данного множества, содержащее k элементов.
Например, из множества M = {1,2,3,4} можно образовать 12 различных размещений, из 4 по 2:
{1, 2} {1, 3} {1, 4} {2, 3} {2, 4} {3, 4}
{2, 1} {3, 1} {4, 1} {3, 2} {4, 2} {4, 3}
Программа. Число размещений из n элементов по k элементов.
Procedure placement(n,k:integer; var r:longint); var i:integer; begin r:=1; for i:=1 to k do r:=r*(n-i+1) end;Сравнивая формулы сочетания и размещения из n элементов по k, получим такое соотношение. $$A_{n}^{k}=C_{n}^{k}\cdot k!$$ Теперь понятно, что для получения размещений достаточно получить сочетания и переставить элементы каждого сочетания.
Таким образом, нужно использовать не только процедуру вырабатывающую сочетания, но и процедуру перестановок из этих сочетаний. Комбинация этих процедур дает необходимый результат. На основе этих рассуждений составим программу решения следующего примера.
Пример. Составить программу вывода на экран размещений из n элементов по k элементов. Заданным массивом являются натуральные числа от 1 до n.
Программа. Генератор размещений
Program generator_placement;
{Размещения из n элем. по k}
const
n1=100;
type
t=array[1..n1] of integer;
var
x,min,max:t;
k,n:integer;
r:longint;
{-----------------------------------------}
Procedure output_p(x:t; k:integer);
{Процедура вывода элементов перестановки на экран}
var
e:integer;
begin
writeln('Размещения элементов');
for e:=1 to k do write(x[e]:4);
writeln
end;
{-----------------------------------------}
Procedure generator_transp(x:t; k:integer;
{Генератор перестановок}
var z:longint);
label 1;
var
y,i,j,v,l:integer;
begin
z:=1;
for i:=1 to k do z:=z*i; {Вычисление числа перестановок}
output_p(x, k);
y := 1;
for y := 2 to z do Цикл по числу перестановок}
begin
i := 2; j := 1;
while x[i - 1] <= x[i] do i := i + 1;
while x[j] <= x[i] do j := j + 1;
v := x[i]; x[i] := x[j]; x[j] := v;
if i = 2 then goto 1;
for l := 1 to (i - 1) div 2 do
begin
v := x[l]; x[l] := x[i - l]; x[i - l] := v
end;
1: output_p(x, k)
end
end;
{-----------------------------------------}
Procedure gen_comb(x,min,max:t; n,k:integer; var r:longint);
var
i,j:integer;
z:longint;
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
generator_transp(x, k, z);
r := r + z; 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);
write('Введ. число эл. по сколько выбирать k = ');
readln(k);
writeln('Размещения из ', n, ' элементов по ',k,' элементов');
gen_comb(x, min, max, n, k, r);
writeln('Число всех размещений равно r = ', r)
end.
