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

Получение полного набора некоторых комбинаторных объектов является важной задачей дискретных вычислений. Например, решение многих задач дискретной оптимизации почти всегда связано с перебором объектов некоторого полного набора. Число r-элементных подмножеств из n-элементного множества равно числу сочетаний:

.

Количество всех подмножеств n-элементного множества равно:

.

Алгоритм получения полного набора подмножеств представим в виде программы на языке С++.

Используется алгоритм перебора бинарных кодов, представляющих искомые подмножества. Бинарный код подмножества представлен массивом типа unsigned char, при этом в 1 байт – элемент массива записывается 1 бит бинарного кода. Однако эту же идею можно реализовать и для носителя подмножества типа битового вектора.

Множество представлено битовым вектором d: