Формула включений-исключений

Применяется в задачах, где необходимо найти количество элементов в объединении некоторого числа множеств, которые могут пересекаться между собой.

Случай 2 множеств

$$|A \cup B| = |A| + |B| - |A \cap B|$$

Складываем размеры множеств. Заметим, что мы дважды учли элементы которые встречаются в обоих множествах. Компенсируем это вычитая количетсво элементов в пересечении множеств.

Случай 3 множеств

$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B|- |A \cap C| - |B \cap C| + |A \cap B \cap C|$$

Пути

Общий случай

$$|\bigcup ^n_{i=1}A_i| = \sum _i|A_i| - \sum _{i<j}|A_i \cap A_j| + \sum _{i<j<k}|A_i \cap A_j \cap A_k| - ... + (-1)^{n-1}|A_1 \cap A_2 \cap ... \cap A_n|$$

Процесс состоит из включения всего, затем исключения ошибочно включенного, затем включения ошибочно исключенного и т.д.

Задача

Отряд из 100 пленных орков вырвался из плена сил альянса. По пути они пробегали через оружейную и схватили кто что мог. В оружейной лежали следующие виды снаряжения: Меч, Щит, Лук. Каждый орк не мог взять несколько предметов одного типа.

Когда отряд отдалился от крепости на достаточное расстояние, их предводитель сделал перекличку. Однако так как он был не самым умным орком, информация полученная им оказалась весьма ограниченной.

Известно что в отряде имеется 48 мечей, 42 щита, 37 брони. Количество орков владеющих мечем или щитом равно 76. Орков ухвативших меч или броню оказалось 76 штук. А владельцев щита или брони - 66 штук. Так же нашллось 5 умельцов схвативших себе все 3 элемента снаряжения.

Для того чтобы продумать оборону, предводителю надо знать количество орков без снаряжения.

Решение Ох лол, сейчас ручками все порешаем

Битовые маски

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

Если у нас небольшое количество множеств, то можно попытаться написать формулу вручную, или оформить её в виде $n$ вложенных циклов. Однако обе эти схемы ломаются, когда мы заранее не знаем число $n$. А при большом числе $n$ количество необходимого кода превышает разумные пределы.

Ниже рассмотрим, как можно использовать битовые маски для упрощения реализации перебора.

Вводная

Битовые операции в C++

Оператор Действие
& И
| ИЛИ
^ Исключающее ИЛИ
~ Дополнение (отрицание)
>> Сдвиг вправо
<< Сдвиг влево
ИИЛИИсключающее ИЛИДополнениеСдвиг вправоСдвиг влево
| | | |--- |--- | |a |1010| |b |0110| |a&b |0010| | | | |--- |--- | |a |1010| |b |0110| |a\|b |1110| | | | |--- |--- | |a |1010| |b |0110| |a^b |1100| | | | |--- |--- | |a |1010| |~a |0101| | | | |--- |--- | |a |1010| |a>>1 |0101| |a>>2 |0010| | | | |--- |--- | |a |1010| |a<<1 |0100| |a<<2 |1000|

Перебор с использованием битовых масок

Пусть у нас имеется 5 множеств: $A_1, A_2, A_3, A_4, A_5$

Закодируем их комбинации с помощью двоичной последовательности длины 5: $11000 = |A_1 \cap A_2|, 10101 = |A_1 \cap A_3 \cap A_5|$

Перебирая все последовательность 0 и 1 длины 5 мы получим все возможные комбинации множеств.

Заведем целочисленную переменную $m$, которая будет принимать все значения от $1$ до $2^{5-1}$. Каждый бит $m_j$ в числе $m$ поставим в соответствие множеству $A_j$. Перебирая все значения числа $m$ мы будем смотреть на значение кадого бита, и принимать решение использовать ли элементы соответствующего множества.

Ниже приведена реализация простого перебора всех возможных значений m:

In [4]:
#include <iostream>
using namespace std;
{
    cout << "Перебираем биты в числе m:"<<endl;
    for(int m = 1; m < (1<<5); ++m) {
        for(int j = 0; j < 5; ++j) {
            cout << (bool)((1 << j) & m); //проверяем j'тый бит в числе m, преобразование к (bool) вернет 0 или 1
        }
        cout << endl;
    }
}
Перебираем биты в числе m:
10000
01000
11000
00100
10100
01100
11100
00010
10010
01010
11010
00110
10110
01110
11110
00001
10001
01001
11001
00101
10101
01101
11101
00011
10011
01011
11011
00111
10111
01111
11111
In [ ]: