ЛЕКЦИЯ 3. Существуют разные подходы к представлению множества:

Множества.

Существуют разные подходы к представлению множества:

1.Хранится каждый элемент, присутствующий в множестве. Это может быть смежное представление (например, массив элементов) или связанное размещение элементов в памяти (в дальнейшем рассмотрим организацию связанных списков).

2.Определяются все потенциально возможные злементы множества А: А={а₀, а_1, .....а_n-2, а_n-1}. Всего n элементов. Затем для каждого подмножества X из А определяется для каждого элемента, принадлежит ли он этому подмножеству. Для этого каждому множеству сопоставляется бинарная (т.е. состоящая из 0 и 1) последовательность b₀,b₁,…b_n-1, определяемая так:

i=0,1,2,...n-1

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

Вектор b= {b₀,b₁,…b_n-1} называется характеристическим вектором из n элементов. Это представление удобнее тем, что основные операции над множествами можно выполнять как побитовые операции над двоичными векторами. Однако для больших n использование таких векторов практически невыполнимо.

Рассмотрим задачу формирования различных подмножеств заданного массивом множества А={а₀, а_1, .....а_n-2, а_n-1}. Заводят некоторую строку битов и устанавливают взаимно-однозначное соответствие между битами строки b и числами из А: b_i <=> а [i].

b: а[n-1] а[n-2].... а[2] а[1] а[0]

.......

.......

n-1 n-2 2 1 0

Описать переменную b можно, например, так

unsigned int b; // если n<32

или

unsigned char b [NN]; // если n<NN*8

Рассмотрим такое описание b:

unsigned int b;

Пусть в переменной b записана информация о некотором подмножестве С⋤А:

i=0,1,2,...n-1

b:

n-1 n-2............. 3 2 1 0

...

.....

Содержимое b есть некоторое целое число

r=, где 0≤ r ≤2ⁿ-1,

т.е. для множества А={а[0], а[1], а[2],.... а[n-2],а[n-1]}

возможны 2ⁿ различных подмножеств.

Как, имея b, получить подмножество элементов из А?

Просматриваем все биты от 0-го до (n-1)-го из b, выводим элементы а[i], соответствующие единичным битам.

Void f1 (int A[], int n, unsigned int b)

{//вывод элементов подмноджества, заданного строкой b

cout<<’\n’;

...

.....

int m=1;

b:

n-1 n-2............. 3 2 1 0

for (int i=0; i<n; i++)

{if (b&m) cout<<а[i]<<” ”;

m<<=1;

}

cout<<’\n’;

}

Void f2 (int а[ ], int n, unsigned char b [ ])

{//вывод элементов подмножества, заданного массивом b.

int j=0, m=0;

cout<<’\n’;

for (int i=0; i<n; i++)

if (b[j] & 1<<m)

{ cout<<а[i]<<” ”;

m++;

if (m==8){m=0; j++;}

}

cout << ’\n’;

}

Как сформировать все подмножества из А?

Так как представление в строке b есть всегда некоторое целое число, то для формирования всех подмножеств можно формировать числа от нуля до 2ⁿ-1(начать с нуля и добавлять по 1 на каждом шаге), их двоичные представления дадут все подмножества n-элементного множества.

unsigned int b=0, k=(1<<n)-1; //k=0000…..0111111111

while (b<k) // n

{b=b+1;

//обработка подмножества, заданного битовой строкой b

Дата добавления: 2014-01-06