Перестановки

Перестановки описывают, сколькими способами можно расставить N различных предметов на N различных позиций.

Число перестановок принято обозначать Pn. N различных элементов можно расставить на N различных мест N! способами. Следовательно, Pn = N! = 1*2*… *(N-1)*N.

Также важной задачей является не только подсчет количества перестановок, но и их генерация, при этом больший интерес представляет генерация перестановок в определенном порядке, например, лексикографическом (отсортированном по возрастанию).

Рассмотрим задачу генерации всех перестановок N-элементного множества в лексикографическом порядке. В качестве примера рассмотрим перестановку для N=3

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Алгоритм генерации следующей перестановки таков: начиная с конца перестановки находим такой элемент a[i]: a[i-1]<a[i]; затем в конце перестановки находим элемент a[j] больший чем a[i-1]; далее меняем местами элементы перестановки a[i-1] и a[j]; и оставшуюся конечную часть перестановки упорядочиваем в порядке возрастания.

{ программа генерации перестановок N элементного
множества в лексикографическом порядке }

Program perms;
var
i, j, h, n, k: integer;
a:array[0 .. 100] of integer; { массив для хранения перестановки }

{процедура вывода полученной перестановки}
procedure output;
var i: integer;
begin
writeln;
for i:=1 to n do write(a[i],' ');
end;

begin
write('количество элементов перестановки: '); readln(n);
fillchar(a, sizeof(a), 0);

{ ввод элементов начальной перестановки }
for i:=1 to n do a[i]:=i;

repeat
output; { вывод текущей перестановки }
i:=n;
while a[i-1]>a[i] do dec(i); { поиск скачка }
j:=i-1;
h:=a[j];
while a[i+1]>h do inc(i); { поиск первого меньшего элемента }
a[j]:=a[i]; a[i]:=h;
i:=j+1; k:=n;
while i<k do begin { перестановка ”хвоста” }
h:=a[i]; a[i]:=a[k]; a[k]:=h;
inc(i); dec(k)
end
until j=0;
end.


Для получения всех n! перестановок необходимо, чтобы начальная перестановка образовывала возрастающую последовательность (то есть была первой в лексикографическом порядке). Следует прокомментировать следующие два момента: почему условием окончания работы программы является выполнение равенства j=0 и почему для упорядочивания хвоста перестановки используется простой цикл без всяких сравнений.
Следуя логике алгоритма, последняя перестановка представляет собой убывающую последовательность. Следовательно, позиция скачка будет равна 1 и соответственно j=0. Ни в каком другом случае равенство j=0 не выполняется, так как тогда перестановка не будет убывающей последовательностью, то есть не является последней.
Об упорядочивании хвоста следует сказать только одно: хвост всегда представляет убывающую последовательность, поэтому требуется его только инвертировать.

Сочетания

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

Рассмотрим задачу о генерации сочетаний в лексикографическом порядке.
Для примера рассмотрим начальные данные N=6 и M=4. Тогда число сочетаний равно 15. Начальное сочетание образует последовательность 1, 2, .. m, а последнее n-m+1, … , n.

1234 1256 2345
1235 1345 2346
1236 1346 2356
1245 1356 2456
1246 1456 3456

Переход к следующему сочетанию осуществляется по следующему правилу: требуется просмотреть текущее сочетание с конца и найти элемент, который можно увеличить. То есть такой элемент что a[i] <> n-k+i. Далее увеличиваем этот элемент на 1, а оставшуюся часть сочетания заполняем числами натурального ряда большими измененного элемента в порядке их следования.

program sochets;
var
i, j, n, m: integer;
a: array[0 .. 100] of integer;

{ процедура вывода текущего сочетания }
procedure use;
var i: integer;
begin
writeln;
for i:=1 to m do write(a[i]:3)
end;

begin
write('ввод N и M: '); read(n, m);

{ формирование первого сочетания }
for i:=0 to m do a[i]:=i;

repeat
use;
i:=m;
while a[i]=n-m+i do dec(i); { поиск элемента для изменения }
inc(a[i]);
for j:=i+1 to m do a[j]:=a[j-1]+1; { изменение правой части сочетания }
until i=0;
end.

Рекурсивный алгоритм генерации сочетаний (с повторениями):

const
n = 3;
k = 2;

procedure s_pov(s: string);
var i: integer;
begin
if length(s) = n then begin
for i := 1 to length(s) do
write(s[i] + ' ');
writeln;
end
else
for i := k downto 1 do
s_pov(s+chr(ord('0') + i));
end;

begin
s_pov('');
end.


Подмножества

Для генерации всех подмножеств N-элементного множества: введем массив b[1..n] такой, что если b[i]=1 то i-й элемент входит в подмножество и если b[i]=0, то иначе. Тогда пустому подмножеству будет соответствовать набор из 0, а n-элементному подмножеству набор из 1. Поэтому здесь явно заметна связь с двоичным представление чисел в интервале 0 … 2N–1.

Будем находить двоичное представление числа и формировать характеристические вектора подмножеств. Изначально положим b[i]=0 для всех I, что соответствует пустому подмножеству. Введем массив a[1..n] соответствующий двоичному представлению числа. Будем моделировать операцию сложения этого числа с 1. Для этого просмотрим число справа налево, заменяя единичные биты на нулевые до тех пор, пока не найдем нулевой бит, который заменим на 1.

program subsets;
var
i, n: integer;
a, b: array[0..100] of integer;

procedure output;
var i : integer;
begin
{ вывод двоичного числа }
for i:=1 to n do write(' ',a[i]);
write(' ');

{ вывод характеристического вектора подмножества }
for i:=1 to n do write(' ',b[i]);
write(' ');

{ вывод подмножества }
for i:=1 to n do
if(b[i]=1) then write(' ',i);
end;

begin
readln(n);
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
repeat
output;
i:=n;
while a[i]=1 do begin
a[i]:=0; dec(i); { перенос в следующий разряд }
end;
a[i]:=1;
b[i]:=1-b[i] { b[i] = (1+b[i]) mod 2 }
until i=0;
end.