Добавил:
Upload
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:kombinatorika-tkg.pdf
X
- •Учебное пособие
- •Тема. Комбинаторика
- •Биномиальные коэффициенты
- •Бином Ньютона
- •Треугольник Паскаля
- •Разбиения множества
- •Числа Стирлинга второго рода
- •Число Белла
- •Числа Стирлинга первого рода
- •Формулы включений и исключений
- •Лекция 5. Производящие функции. Основные операции. Примеры использования.
- •Производящие функции
- •Основные операции
- •Примеры использования ПФ
- •Лекция 6. Генерирование комбинаторных объектов. Перестановки. Сочетания. Разбиение чисел. Подмножества множеств.
- •Перестановки
- •Сочетания
- •Разбиения чисел
- •Подмножества множества
- •Тема. Теория конечных графов
- •Ребро
- •Цвет
- •Букет
- •Букет
- •Пуст
- •Лекция 1. Введение в комбинаторику.
- •Некоторые области применения задач комбинаторики.
Подмножества множества
Порождение подмножеств множества (a1,a2,…,an) эквивалентно порождению n - разрядных двоичных наборов: ai принадлежит подмножеству, если и только если i-й разряд равен единице. Таким образом, задача порождения всех подмножеств множества сводится к задаче порождения всех возможных двоичных последовательностей длины n.
Следующий алгоритм описывает эту процедуру:
Листинг 6.4 Алгоритм генерации подмножеств множества. for i=0 to n do bi ←0;
while bn≠1 do begin
вывести (bn-1bn-2…b0); i←0;
while bi=1 do begin
bi ←0;
i ← i+1;
end;
bi ← 1;
end.
25
Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]