.: Компьютерный учебник- Процедурно-ориентированное программирование :.

.: [предыдущая | оглавление | следующая] :.

9.2 Генерация подмножества

Общее число подмножеств для данного множества E может быть подсчитано на основе следующей формулы:

(9.1)
где n - мощность исходного множества. Таким образом, каждому подмножеству можно поставить в соответствие некоторое число i. Двоичное представление этого числа даст однозначное соответствие между числом и подмножеством. Например, дана следующая таблица для множества {a, b, c} :

Число	a	b	c
0	0	0	0
1	0	0	1
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1
6	1	1	0
7	1	1	1

Тогда все множество подмножеств без учета пустого множества будет {c, b, cb, a, ca, cb, cba}.

Можно предложить следующий алгоритм генерации подмножества некоторого множества En по номеру k :

каждому элементу множества ставим в соответствие некоторый индекс j.
записываем двоичное представление номера k.
в подмножество записываем те элементы множества, индексы которых соответствуют позиции единиц в двоичном представлении номера k.

Пример программы генерации показан ниже. Здесь используется механизм выделения бита в двоичном числе. Предполагается также, что мощность множества не превышает количества разрядов в двоичном числе. После работы функции в векторе v будут содержаться единицы в соответствии с двоичным числом num.

void GenerateSubset(int v[ ],int size, unsigned num)
{
      int ed=1;
      for (int i=0; i<size; i++){
            if (ed&num) v[i]=1 ; else v[i]=0; //проверяем соответствующий разряд
      ed <<= 1; //сдвиг влево на один разряд
      }
}

.: [предыдущая | оглавление | следующая] :.