ЛЕКЦИЯ 3.
Множества.
Существуют разные подходы к представлению множества:
1.Хранится каждый элемент, присутствующий в множестве. Это может быть смежное представление (например, массив элементов) или связанное размещение элементов в памяти (в дальнейшем рассмотрим организацию связанных списков).
2.Определяются все потенциально возможные злементы множества А: А={а0, а1, . . . . .аn-2, аn-1}. Всего n элементов. Затем для каждого подмножества X из А определяется для каждого элемента, принадлежит ли он этому подмножеству. Для этого каждому множеству сопоставляется бинарная (т.е. состоящая из 0 и 1) последовательность b0,b1,…bn-1, определяемая так:
i=0,1,2, . . .n-1
Наилучший метод представления множеств существенно зависит от операций, которые планируется выполнять над множествами. Это типичные операции: выяснить, имеется ли конкретный элемент в данном множестве, добавить в множество новые элементы, удалить из множества элементы, выполнить обычные теоретико-множественные операции, например объединение или пересечение двух множеств.
Вектор b= {b0,b1,…bn-1} называется характеристическим вектором из n элементов. Это представление удобнее тем, что основные операции над множествами можно выполнять как побитовые операции над двоичными векторами. Однако для больших n использование таких векторов практически невыполнимо.
Рассмотрим задачу формирования различных подмножеств заданного массивом множества А={а0, а1, . . . . .аn-2, аn-1}. Заводят некоторую строку битов и устанавливают взаимно-однозначное соответствие между битами строки b и числами из А: bi <=> а [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 ≤2n-1,
т.е. для множества А={а[0], а[1], а[2], . . . . а[n-2],а[n-1]}
возможны 2n различных подмножеств.
Как, имея 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 есть всегда некоторое целое число, то для формирования всех подмножеств можно формировать числа от нуля до 2n-1(начать с нуля и добавлять по 1 на каждом шаге), их двоичные представления дадут все подмножества n-элементного множества.
unsigned int b=0, k=(1<<n)-1; //k=0000…..0111111111
while (b<k) // n
{b=b+1;
//обработка подмножества, заданного битовой строкой b