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

e-maxx algorithm original: C/C++ #algorithm #bit-manipulation #emaxx #math #number-theory

题目文本会按所选界面语言从俄语翻译；代码保持不变。

Static

Источник: e-maxx.ru/algo, страница PDF 47.

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

Дана битовая маска

. it is required эффективно перебрать все её подмаски, т.е. такие маски

, в которых могут

быть включены только те биты, которые были включены в маске

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

int s = m;

while (s > 0) {

... можно использовать s ...

s = (s-1) & m;

}

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

for (int s=m; s; s=(s-1)&m)

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

for (int s=m; ; s=(s-1)&m) {

... можно использовать s ...

if (s==0)  break;

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

Пусть у нас есть текущая подмаска

, и мы хотим перейти к следующей подмаске. Отнимем от маски

единицу, тем

самым мы снимем самый правый единичный бит, а все биты правее него поставятся в

. Затем удалим все

"лишние" единичные биты, которые не 输入ят в маску

и потому не могут 输入ить в подмаску. Удаление

осуществляется битовой операцией

. В результате мы "обрежем" маску

до того наибольшего

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

Особо рассмотрим момент, когда

. После выполнения

мы получим маску, в которой все биты

включены (битовое представление числа

), и после удаления лишних битов операцией

получится

не что иное, как маска

. Поэтому с маской

следует быть осторожным — если вовремя не остановиться

на нулевой маске, то 算法 может войти в бесконечный цикл.

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

Во многих 题目х, особенно на dynamic programming по маскам, it is required перебирать все маски, и для каждой маски - все подмаски:

for (int m=0; m<(1<<n); ++m)

for (int s=m; s; s=(s-1)&m)

... использование s и m ...

Докажем, что внутренний цикл суммарно выполнит

итераций.

证明: 1 способ. Рассмотрим

-ый бит. Для него, вообще говоря, есть ровно три варианта: он

не 输入ит в маску

(и потому в подмаску

); он 输入ит в

, но не 输入ит в

; он 输入ит в

и в

. Всего битов

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

, что и требовалось доказать.

证明: 2 способ. Заметим, что если маска

имеет

включённых битов, то она будет иметь

подмасок. Поскольку масок длины

с

включёнными битами есть

(см. "биномиальные коэффициенты"), то

всего комбинаций будет: Посчитаем эту сумму. Для этого заметим, что она есть не что иное, как разложение в бином Ньютона

выражения

, т.е. , что и требовалось доказать.

C# 解法

自动草稿，提交前请检查

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    int s = m;
    while (s > 0) {
            ... можно использовать s ...
            s = (s-1) & m;
    }
    for (int s=m; s; s=(s-1)&m)
            ... можно использовать s ...
    for (int s=m; ; s=(s-1)&m) {
            ... можно использовать s ...
            if (s==0)  break;
    }
    for (int m=0; m<(1<<n); ++m)
            for (int s=m; s; s=(s-1)&m)
                    ... использование s и m ...
}

C++ 解法

匹配/原始

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

Java 解法

自动草稿，提交前请检查

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    int s = m;
    while (s > 0) {
            ... можно использовать s ...
            s = (s-1) & m;
    }
    for (int s=m; s; s=(s-1)&m)
            ... можно использовать s ...
    for (int s=m; ; s=(s-1)&m) {
            ... можно использовать s ...
            if (s==0)  break;
    }
    for (int m=0; m<(1<<n); ++m)
            for (int s=m; s; s=(s-1)&m)
                    ... использование s и m ...
}

Материал разбит как 算法ическая 题目: изучить постановку, понять асимптотику и реализовать 算法 на выбранном языке.

Vacancies for this task

活跃职位 with overlapping task tags are 已显示.

所有职位

目前还没有活跃职位。