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

Для начала нам нужно сначала понять, в чем проблема и ее корни. Мы знаем, что имеем дело с подмножествами, находящимися под фундаментальной дискретной структурой, на которой построены все остальные дискретные структуры, а именно с множеством. Так что же это?

Наборы

Набор – это неупорядоченный набор объектов, называемых элементами или членами набора, которые являются различными. Мы пишем a ∈ A, чтобы обозначить, что a является элементом множества A.

Пример. Множество V всех гласных букв английского алфавита можно записать в виде v = {a, e, i, o, u} (этот способ описания набора называется методом реестра). ).

Другой пример использования метода построителя наборов для описания: O = {x | x — нечетное положительное целое число, меньшее 10}.

Два множества равны тогда и только тогда, когда они состоят из одних и тех же элементов. например, {1, 2, 3} и {3, 1, 2} равны, потому что они имеют одинаковые элементы. Порядок перечисления элементов значения не имеет.

Подмножества

Множество A является подмножеством B тогда и только тогда, когда каждый элемент A также является элементом B . Обозначается как A ⊆ B. Есть несколько полезных правил, позволяющих определить, является ли набор подмножеством;

  1. Чтобы показать, что A ⊆ B, покажите, что если элемент x принадлежит A, то x также принадлежит Б.
  2. Чтобы показать, что A /⊆ B, найдите единственный элемент x такой, что x не является элементом B.

Подчеркивая, что набор A является подмножеством набора B, но что A не равен B, мы говорим, что A является правильным или строгим подмножеством B. Чтобы это было правдой, должно быть так, что A является подмножеством B и должен существовать элемент x B, который не является элементом A.

Пусть S — множество, если в S ровно n различных элементов, где n — целое неотрицательное число, мы говорим, что S — конечное множество, а n — мощность множества S, которая обозначается |S|. Другими словами, мощность — это размер множества. Набор из n элементов имеет 2^n подмножеств. Рассмотрим пример.

Учитывая набор A = {a, b}, ∅, {a}, {b}, {a, b}, все подмножества A. Из этого примера мы можем видеть, что набор из 2 элементов дает нам общее из 4 подмножеств, потому что n = 2 и 2 ^ n = 4. Следовательно,

n = 0: 2^0 = 1
n = 1: 2^1 = 2
n = 2: 2^2 = 4
n = 3: 2^3 = 8
n = 4: 2^4 = 16

Концепция типа данных в области информатики основана на идее множества. Конкретный тип данных — это имя набора вместе с набором операций, которые можно выполнять над элементами этого набора. Примеры включают Boolean, имя множества {0, 1} и его операторы И, ИЛИ и НЕ. Другой пример: int в python {x | x ∈ Z} и операторы +, -, *, / и т.д.

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

  • Пусть A = {a1, a2, …, an}, где n в количестве элементов — это множество.
  • Представлять каждое подмножество A битовой маской длины n, где iбит равен 1 тогда и только тогда, когда ai (для 0 ≤ i ‹ n) принадлежит A. Вы проверяете каждый элемент множества A, скажем, x, и соответствующий элемент в маске, скажем, m, если m равно true или 1, мы добавляем x в таблицу результатов, в противном случае мы игнорируем элемент. Например, mask = [1, 0, 1, 1] и A = [1, 2, 3, 4],переменная результата будет [1 , 3, 4].
  • Чтобы сгенерировать все подмножества A, перечислите все битовые маски 2^n длины n.
  • Выведите соответствующие подмножества.

Пример вывода 1:

Example of generated bit mask when n = 4
0000              1000
0001              1001
0010              1010
0011              1011
0100              1100
0101              1101
0110              1110
0111              1111

Наблюдение 1. Если вы внимательно посмотрите на вывод выше, вы заметите интересную закономерность. Первый блок и второй блок имеют одинаковые биты после старшего бита. Это означает, что изменяются только самые значащие биты. Мы будем использовать это наблюдение для ускорения нашего алгоритма.

Первый алгоритм, который мы напишем, генерирует все подмножества, проходящие через все 2^n возможные результаты. Ниже приведен алгоритм, написанный на Python.

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

Это приведет нас к очень интересному алгоритму под названием Двоичный код Грея, который перечисляет все 2^n строк из n бит таким образом, что каждый раз изменяется только один бит. См. Пример вывода 1 выше.

Как я заметил в своем наблюдении, мы можем использовать маску для представления двоичной последовательности Грея из n-битных строк, а затем определить ее рекурсивно по некоторым правилам.

  1. mask[0] = ‘ ’ # обозначает пустую строку
  2. mask[n + 1] = 0mask[n], 1mask[n]R# 0mask[n] означает последовательность mask[n] с префиксом 0 к каждой строке, а 1mask[n]R означает последовательность mask[n] с префиксом 1 к каждой строке в обратном порядке, следовательно, R.

Так как у mask[n] такое же свойство, то mask[n] состоит из первых элементов 2^n, преобразованных в n-битные строки. вставив 0s слева, если это необходимо. Таким образом, алгоритм посещает все двоичные n-кортежи (an-1, …, a0) в порядке двоичного кода Грея. Код Python ниже демонстрирует эту идею.

В конце концов, этот алгоритм генерирует строку битов для n - 1 ниже

000
001
010
011
100
101
110
111

но это строки с 9 по 16, которые вставляют префиксы 0 и 1 и, наконец, определяют само подмножество в строке 10.

Этот алгоритм поддерживает массив f. так что мы можем многократно формировать (an-1, …, a0)2, дополняя j-й бит, как мы должны.

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

использованная литература