UniLecs #108. Теория множеств

UniLecs

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

Входные данные: N - натуральное число от 1 до 10. Элементы заданного множества - натуральные числа от 1 до N.

Вывод: кол-во всевозможных подмножеств, а также все эти подмножества, кроме пустого.

Пример: N = 2; Кол-во: 4;

Подмножества: { 1, 2, 12 } (пустое множество можно не выводить)

Идея: эту задачу условно можно разбить на две подзадачи:

Определение кол-ва подмножеств заданного множества из N элементов.
Генерация и вывод всех подмножеств заданного множества из N элементов.

Кол-во подмножеств заданного множества из N элементов

Проведем аналогию с битами.

В одной ячейке храниться либо 1 либо 0. 2^1 = 2 элемента.

Две ячейки: 00, 01, 10, 11. Число состояний в 2х ячейках равно 2^2 = 4.

Для 3-х: 2^3 = 8.

Для N: 2^N.

Пусть множество A состоит из одного элемента a: A={a}, т.е. n = 1. Число подмножеств множества A будет равно 2, так как подмножествами A являются:

- подмножество A={a}, состоящее из единственного элемента множества A, и

- пустого множество ∅.

По сути для множеств можно установить соот-вие:

- если бит равен 1, то этому состоянию ставим в соответствие существование элемента a;

- если бит равен 0, то этому состоянию ставим в соответствие несуществование элемента a.

Теперь рассмотрим множество A={a1, a2, ..., an}. Подмножества A получаются из множества A удалением одного или более (до n) элементов. Можно поставить в соответствие удаленным элементам 0, а не удаленным 1. Тогда ясно, что число подмножеств множества A равно 2n.

Смотри рисунок ниже:

Получаем формулу для вычисления числа подмножеств заданного множества из N элементов: K = 2^N

Еще один способ для нахождения числа всех подмножеств:

1 << N - это побитовый сдвиг единицы на N позиций влево.

Генерация и вывод всех подмножеств заданного множества из N элементов

Для решения этой задачи есть очень элегантный способ с использованием битовых масок и битовых операций.

Давайте рассмотрим на примере для случая N = 4.

В двоичном виде единица выглядит так 00000001. После сдвига на 4 позиции влево появится новое число, двоичный вид которого 00010000. Теперь, если вычесть из этого числа единицу получим: 1111. Четыре единицы — это состояние, когда в подмножество попадают все элементы, 0000 — пустое множество, 1010 — подмножество состоит из первого и третьего элемента множества (нумерация с нуля, отсчет ведется справа) и т.д.

Таким образом мы перебираем числа, двоичное представление которых от 0000 до 1111.

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

Например, на каком-то шаге цикла программы маска равна 1100, мы перебираем все позиции путем сдвига единицы: 0001, 0010, 0100 и 1000. Для проверки воспользуемся операцией побитового И (если в одинаковых позициях стоят единицы, то результат единица, иначе ноль).

В нашем случае:

1100 & 0001 = 0000

1100 & 0010 = 0000

1100 & 0100 = 0100

1100 & 1000 = 1000

Т.е. если в итоге получилось число отличное от нуля, то включаем элемент в множество.

Более детально вы можете ознакомиться тут:

Реализация:

https://gist.github.com/unilecs/75327dbabd87baf7c4a2ec8c94551ca4

Test:

https://dotnetfiddle.net/I86TM1

P.S.

наш канал @UniLecs
наш чат: @UniLecs_Chat

UniLecs #108. Теория множеств

Report Page