Полная версия

Главная arrow Математика, химия, физика arrow Комбинаторные алгоритмы: множества, графы, коды

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

ЗАДАНИЕ 2 Генерация всех подмножеств конечного множества

Во многих переборных алгоритмах необходимо последовательно рассмотреть все подмножества некоторого конечного множества и среди них найти то, которое удовлетворяет заданному условию. Иногда бывает важно, чтобы каждое последующее подмножество отличалось от предыдущего наименьшим образом. Изучить известные методы генерации подмножеств конечного множества и получить практические навыки программной реализации переборных алгоритмов - цель задания.

Формулировка задачи

Пусть задано универсальное конечное множество Х= Дь ..., х„}. Требуется построить все различные его подмножества. Это задача на построение комбинаторных объектов - подмножеств конечного множества. Заметим, что множество X имеет в точности 2" различных подмножеств. Каждое из подмножеств А с X однозначно задается битовой шкалой (яь ..., ап), т. е. двоичным вектором длины п. Значит, построение всех различных подмножеств множества Х=ь ..., х„} можно свести к генерации всех и-разрядных двоичных векторов.

Рассмотрим три популярных алгоритма генерации двоичных векторов [5, 17]. В них двоичные векторы формируются водномерном массиве 5 = (5[1], ..., В[п]) длины п, элементы которого принимают значения 0 и 1. На вход алгоритмов поступает целое число п > 0.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>