Лекции - Структуры и алгоритмы компьютерной обработки данных / 12.Генерация комбинаторных объектов. Перестановки. Размещения. Сочетания
..docГенерация комбинаторных объектов
-
Перебор всех объектов заданного
типа
2. Получить по номеру объекта значение объекта и наоборот.
Перестановки
Перестановка n элементов –последовательность этих элементов в некотором заданном порядке.
Размещения с повторениями
Размещение с повторениями из n по k – последовательность из чисел 1..n длиной k.
Количество размещений с повторениями
n =3, k=2
11 12 13 21 22 23 31 32 33
Генерация размещений с повторениями
procedure generate(n, k: longint);
var i: longint;
begin
if k=0 then print(a)
else
for i:=1 to n do begin
a[k]:=i;
generate(n,k-1);
end;
end;
Задача о рюкзаке
Задан набор n предметов с массами mi и стоимостями ci. Максимальная масса рюкзака M. Выбрать подмножество предметов так, чтобы Σ mi ≤ M и Σ сi → max.
Решение задачи о рюкзаке
Обозначим 1 – берем предмет, 2 – не берем. Тогда каждому набору предметов соответствует размещение из 2 по n.
Пример: n=4
{1,3} → 1212
{4} → 2221
Таким образом перебор подмножеств сводится к перебору размещений с повторениями.
Нумерация размещений с повторениями
Размещению с повторениями соответствует число в системе счисления с основанием n. Значение этого числа можно рассматривать как номер размещения.
Пример: n=3, k=2.
d= 5 = 123 → 23
Размещения без повторений
Размещение без повторений из n по k – последовательность из чисел 1..n длиной k без повторений.
Количество размещений без повторений
n =3, k=2
12 13 21 23 31 32
Генерация размещений без повторений
procedure generate(n, k: longint; s:intset);
var i: longint;
begin
if k=0 then print(a)
else
for i:=1 to n do
if not (i in s) then begin
a[k]:=i;
generate(n,k-1,s+[i]);
end;
end;
Нумерация аналогична нумерации перестановок.
Сочетания
Сочетание из n по k – множество из чисел 1..n имеющее k элементов.
Количество сочетаний
n =3, k=2
12 13 23
Рекуррентное тождество
1 |
|
|
|
|
|
|
|
1 |
1 |
|
|
|
|
|
|
1 |
2 |
1 |
|
|
|
|
|
1 |
3 |
3 |
1 |
|
|
|
|
1 |
4 |
6 |
4 |
1 |
|
|
|
1 |
5 |
10 |
10 |
5 |
1 |
|
|
1 |
6 |
15 |
20 |
15 |
6 |
1 |
|
1 |
7 |
21 |
35 |
35 |
21 |
7 |
1 |
Треугольник Паскаля
Генерация сочетаний
Type intset = set of byte;
procedure Generate(n,k: integer; s:intset);
begin
if n>=k then
if k=0 then Print(S)
else begin
Generate(n-1,k-1,s+[n]); Generate(n-1,k,s);
end;
end;
Var n,k: integer;
begin
Readln(n,k); Generate(n,k,[]);
end.