Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Лекции - Структуры и алгоритмы компьютерной обработки данных / 12.Генерация комбинаторных объектов. Перестановки. Размещения. Сочетания

..doc
Скачиваний:
104
Добавлен:
06.02.2015
Размер:
54.27 Кб
Скачать

Генерация комбинаторных объектов

      1. Перебор всех объектов заданного

типа

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 и Σ сimax.

Решение задачи о рюкзаке

Обозначим 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.