Размещения из 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, мы будем обозначать символом , оно оп-ределяется по формуле: $$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 элементов.

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.