\Section{Динамика по подмножествам}{2 ноября}{Илья Кайсин}

\Subsection{Представление множеств}

Подмножества $n$-элементного множества (например, множества чисел от $0$ до $n - 1$) можно задавать последовательностями из $n$ нулей и единиц естественным образом (<<0>> --- берём элемент, <<1>> --- не берём). Поэтому в программе множество удобно представлять числом, битовая запись которого совпадает с заданием этого множества строкой из нулей и единиц. 

\Subsection{Операции с множествами}

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

\Subsubsection{Объединение}

$C = A \cup B = \{x \mid x \in A \vee x \in B\}$

\begin{code}
	unsigned char a = 72;    // 01001000
	unsigned char b = 184;   // 10111000 
	unsigned char c = a | b; // 11111000 = 248 

\end{code}



\Subsubsection{Пересечение}

$A \cap B = \{x \mid x \in A \wedge x \in B\}$

\begin{code}
	unsigned char a = 72;    // 01001000
	unsigned char b = 184;   // 10111000 
	unsigned char c = a & b; // 00001000 = 8

\end{code}

\Subsubsection{Дополнение}

$C = \overline{A}$

\begin{code}
	unsigned char a = 184; // 10111000 
	unsigned char c = ~a;  // 01000111 = 71
\end{code}

\Subsubsection{Симметрическая разность}

$C = A \triangle B$

\begin{code}
	unsigned char a = 72;    // 01001000
	unsigned char b = 184;   // 10111000 
	unsigned char c = a ^ b; // 11110000 = 240
\end{code}

\Subsubsection{Разность}

Существует несколько способов найти разность множеств. 

$A \setminus B = A \cap \overline{B} = A \triangle (A \cap B)$

\begin{code}
	unsigned char a = 184;         // 10111000 
	unsigned char b = 73;          // 01001001
	unsigned char c = a ^ (a & b); // 10110000 = 176
	unsigned char d = a & (~b);    // 10110000 = 176
\end{code}

\Subsubsection{Одноэлементные множества}

Заметим, что одноэлементные множества задаются степенями двойки, которые легко вычислить с помощью операции битого сдвига.

$A = \{x\}$

\begin{code}
	int x = 4; // [0, 8)
	unsigned char a = 1 << x; // 00010000 = 16
\end{code}

\Subsubsection{Добавление элемента в множество}

Для того, чтобы добавить элемент $x$ в множество $A$, нужно множество $A$ объединить с одноэлементным множеством $\{x\}$.

$B = A\cup \{x\}$

\begin{code}
	int x = 6; // [0, 8)
	unsigned char a = 184;          // 10111000  
	unsigned char b = a | (1 << x); // 11111000
\end{code}

Если элемент уже существовал в множестве, естественно, повторно он добавлен не будет.

\Subsubsection{Удаление элемента из множества}

Для того, чтобы удалить $x$ из множества $A$, нужно из $A$ вычесть одноэлементное множество $\{x\}$. Или, если мы знаем, что элемент в множестве точно был, найти симметрическую разность $A$ и $\{x\}$.

$B = A \setminus \{x\}$
или
$B = A \triangle \{x\}$

\begin{code}
	int x = 5; // [0, 8)
	unsigned char a = 184;          // 10111000  
	unsigned char b = a ^ (1 << x); // 10011000
\end{code}

\Subsubsection{Проверка принадлежности}

$x \in A \Leftrightarrow A \cap \{x\} \neq \varnothing$

\begin{code}
	int x = 5; // [0, 8)
	int y = 6; // [0, 8)
	unsigned char a = 184;   // 10111000  
	bool inx = (1 << x) & a; // 00100000, true
	bool iny = (1 << y) & a; // 00000000, false
\end{code}

\Subsection{Динамика по подмножествам}

Основная идея в том, что мы можем посчитать значение функции для какого-то множества, зная значения функци для одного или нескольких его собственных (не совпадающих со всем множеством) подмножеств.

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

Например, если задавать подмножества $n$-элементного множества беззнаковыми целыми числами от $0$ до $2^{n} - 1$ (что подробно описано в предыдущей части), нас устроит порядок $0 \dots 2^{n} - 1$, поскольку любое (собственное) подмножество описывается меньшим числом. 

Кроме того, для пересчёта динамики нужно научиться перебирать подмножества. О том, как перебирать все подмножества, будет сказано в одной из следующих глав, а для тех задач, которые будут рассмотренны в этой главе, достаточно переходить к подмножеству без минимального элемента. Научимся делать это, извлекая младший значащий бит. 

\Subsubsection{Младший бит}

Пусть число $a$ в двоичной системе имеет вид '$\dots\overbrace{10 \dots 0}^{\text{$k$ бит}}$'. Тогда число \textasciitilde$a + 1$ совпадает с $a$ ровно в последнийх $k$ битах, а в остальных отличается. Поэтому если применить побитовое <<и>> к $a$ и \textasciitilde$a + 1$ , мы как раз получим последний кусок '10\dots 0'. 

\begin{code}
	unsigned char a = 184;          // 10111000
	unsigned char b = a & (~a + 1); // 00001000
/*
           a = 10111000
          ~a = 01000111
      ~a + 1 = 01001000
a & (~a + 1) = 00001000
*/
\end{code}

Однако избавляться от младшего бита можно несколько проще: $a \& (a - 1)$. Корректность этой операции легко проверить аналогичнми рассуждениями. 

\begin{code}
	unsigned char a = 184;          // 10111000
	unsigned char b = a & (a - 1);  // 10110000
/*
           a = 10111000
       a - 1 = 10110111
 a & (a - 1) = 10110000
*/
\end{code}


Рассмотрим несколько примеров.

\Subsubsection{Суммы на подмножествах}

Даны $n$ предметов. Вес $i$-го предмета --- $w_i$. Требуется найти суммарный вес каждого подмножества предметов. 

Сложность алгоритма --- $\O(2^n)$.

\begin{code}
	sum[0] = 0;
	for (int i = 0; i < n; ++i)
		sum[1 << i] = w[i];

	for (int mask = 1; mask < (1 << n); ++mask) {
		int e = mask & (~mask + 1);
		sum[mask] = sum[e] + sum[mask ^ e];
	}
\end{code}
	
\Subsubsection{Количество единиц в числе}

Для каждого числа от $0$ до $2^{n} - 1$ посчитать количество единиц в его битовой записи.
Задачу можно свести к предыдущей: теперь вес каждого предмета --- 1. Но рассмотрим немного другое решение, тоже за $\O(2^n)$.

\begin{code}
	sum[0] = 0;
  
	for (unsigned int mask = 1; mask < ((unsigned int)1 << n); ++mask) {
		sum[mask] = sum[mask >> 1] + (mask & 1);
	}
\end{code}

Здесь мы перешли не к подмножеству, а просто уменьшили число, сдвинув его на 1 вправо. C операцией '$>>$' нужно работать аккуратно, поскольку для знаковых чисел такой сдвиг --- Implementation-defined behaviour.

\Subsection{Гамильтонов путь и цикл}

\begin{Def}
	Гамильтонов путь --- простой путь, проходящий через каждую вершину графа ровно один раз.
\end{Def}
\begin{Def}
	Гамильтонов цикл --- замкнутый гамильтонов путь.
\end{Def}

\Subsubsection{Гамильтонов путь}

Дан неориентированный граф на $n$ вершинах. Найти в нём гамильтонов путь.

Простая динамика: $is_{A, v}$ --- есть ли гамильтонов путь в подграфе, индуцированном на множестве вершин $A$ ($A$ --- маска), оканчивающийся в вершине $v$ ($v \in A$). 

База: $A_{\{{v}\}, v} = 1;$ Переход: переберём все смежные с $v$ вершины, лежащие в множестве $A$. $is_{A, v} = 1$ только в том случае, если для какой-то перебираемой вершины $u$ (смежной с $v$) существовал гамильтонов путь, оканчивающийся в $u$ и проходящий по множеству $A \setminus \{v\}$.

Сейчас требуется $\Theta(2^n n^2)$ времени и $\Theta(2^n n)$ памяти. Память можно сократить до $\Theta(2^n)$, если вместо двумерного массива $is$ нулей и единиц хранить одномерный массив масок $fin$: $fin_A$ --- маска вершин, в которых может заканчиваться гамильтонов путь по множеству $A$.

Чтобы соптимизировать время до $\Theta(2^n n)$, будем хранить в битовом виде ещё и матрицу смежности: $adj_v$ --- множество вершин, смежных с $v$. Теперь заменим перебор всех соседей вершины на одну битовую операцию: $fin_{A, v} = fin_{A \setminus v} \& adj_v$ ($fin_{A, v}$ --- $v$-й бит маски $fin_A$).

\begin{code}
	// fin = {0, ..., 0}
	for (int i = 0; i < n; ++i)  
		fin[1 << i] = 1 << i;
							  
	for (int mask = 1; mask < (1 << n); ++mask) 
		for (int v = 0; v < n; ++v) 
			if (mask & (1 << v) && mask != (1 << v)) 
				if (fin[mask ^ (1 << v)] & adj[v]) 
					fin[mask] |= (1 << v);

\end{code}

\Subsubsection{Гамильтонов цикл}

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

Задача нахождения гамильтонова пути, начинающегося в вершине $0$ решается точно такой же динамикой. 

Единственным отличием будет база: 

\begin{code}
	fin[1] = 1;
\end{code}

\Subsubsection{Восстановление ответа}

Поймём, как по посчитанной динамике восстановить ответ.  

Мы для каждого подмножества знаем те вершины, в которых заканчивается гамильтонов путь, проходящий по этому подмножеству. Назовём такие вершины конечными для данного подмножества. Возьмём множество всех вершин и удалим из него любую конечную, предварительно добавив в ответ. Мы перешли к множеству, в котором меньше вершин на одну. Следующей вершиной в пути должна быть вершина, смежная с предыдущей, причём конечная для текущего подмножества. Такая, конечно, найдётся, ведь динамика посчитана корректно. Добавим её в ответ и удалим. Будем так делать до тех пор, пока вершин не останется.

Гамильтонов цикл восстанавливается аналогично, за исключением того, что первой вершиной выбирается не любая конечная, а смежная с $0$.
