MAXimal

добавлено: 16 Jan 2009 0:58
редактировано: 25 Apr 2012 3:11

Перебор всех подмасок данной маски

Перебор подмасок фиксированной маски

Дана битовая маска m. Требуется эффективно перебрать все её подмаски, т.е. такие маски s, в которых могут быть включены только те биты, которые были включены в маске m.

Сразу рассмотрим реализацию этого алгоритма, основанную на трюках с битовыми операциями:

int s = m;
while (s > 0) {
	... можно использовать s ...
	s = (s-1) & m;
}

или, используя более компактный оператор for:

for (int s=m; s; s=(s-1)&m)
	... можно использовать s ...

Единственное исключение для обоих вариантов кода — подмаска, равная нулю, обработана не будет. Её обработку придётся выносить из цикла, или использовать менее изящную конструкцию, например:

for (int s=m; ; s=(s-1)&m) {
	... можно использовать s ...
	if (s==0)  break;
}

Разберём, почему приведённый выше код действительно находит все подмаски данной маски, причём без повторений, за O (их количества), и в порядке убывания.

Пусть у нас есть текущая подмаска s, и мы хотим перейти к следующей подмаске. Отнимем от маски s единицу, тем самым мы снимем самый правый единичный бит, а все биты правее него поставятся в 1. Затем удалим все "лишние" единичные биты, которые не входят в маску m и потому не могут входить в подмаску. Удаление осуществляется битовой операцией \& m. В результате мы "обрежем" маску s-1 до того наибольшего значения, которое она может принять, т.е. до следующей подмаски после s в порядке убывания.

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

Особо рассмотрим момент, когда s = 0. После выполнения s-1 мы получим маску, в которой все биты включены (битовое представление числа -1), и после удаления лишних битов операцией (s-1) \& m получится не что иное, как маска m. Поэтому с маской s = 0 следует быть осторожным — если вовремя не остановиться на нулевой маске, то алгоритм может войти в бесконечный цикл.

Перебор всех масок с их подмасками. Оценка 3^n

Во многих задачах, особенно на динамическое программирование по маскам, требуется перебирать все маски, и для каждой маски - все подмаски:

for (int m=0; m<(1<<n); ++m)
	for (int s=m; s; s=(s-1)&m)
		... использование s и m ...

Докажем, что внутренний цикл суммарно выполнит O (3^n) итераций.

Доказательство: 1 способ. Рассмотрим i-ый бит. Для него, вообще говоря, есть ровно три варианта: он не входит в маску m (и потому в подмаску s); он входит в m, но не входит в s; он входит в m и в s. Всего битов n, поэтому всего различных комбинаций будет 3^n, что и требовалось доказать.

Доказательство: 2 способ. Заметим, что если маска m имеет k включённых битов, то она будет иметь 2^k подмасок. Поскольку масок длины n с k включёнными битами есть C_n^k (см. "биномиальные коэффициенты"), то всего комбинаций будет:

 \sum_{k=0}^n C_n^k 2^k.

Посчитаем эту сумму. Для этого заметим, что она есть не что иное, как разложение в бином Ньютона выражения (1+2)^n, т.е. 3^n, что и требовалось доказать.