Генерация всех подмножеств набора

При определении всех подмножеств данного набора решающую роль играет количество элементов (n) . Для достижения этой цели эффективный алгоритм использует рекурсивные методы.

Рекурсивный алгоритм

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

Начиная с n=1, у нас есть два подмножества: {} (пустое множество) и {1}.

Для n>1 мы определяем подмножества 1,...,n-1 и дублируйте их. В один набор к каждому подмножеству будет добавлено n, а другой останется неизменным. Объединение этих двух наборов дает полный набор подмножеств.

Иллюстративный пример

Давайте сгенерируем подмножества {1, 2, 3, 4, 5}:

• n=1: {{} , {1}}
• n=2: Возьмите {} , {1} и добавьте 2. Объединение с {} , {1}: {{} , {1} , {2} , {1, 2}}
• n=3: Добавьте 3: {{} , {1} , {2} , {1, 2}, {3} , {1, 3} , {2, 3} , {1, 2, 3}}
• n=4: Добавьте 4: {{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}, {4}, {1, 4}, {2, 4}, {1, 2, 4}, {3, 4}, {1, 3, 4}, {2, 3, 4}, { 1, 2, 3, 4}}
• n=5: Добавьте 5: {{} , {1} , {2} , {1, 2} , {3} , {1, 3}, {2, 3}, {1, 2, 3}, {4}, {1, 4}, {2, 4}, {1, 2, 4}, {3, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}, {5}, {1, 5}, {2, 5}, {1, 2, 5}, {3, 5}, {1, 3, 5}, {2, 3, 5}, {1, 2, 3, 5}, {4, 5}, {1, 4, 5}, {2, 4 , 5} , {1, 2, 4, 5} , {3, 4, 5} , {1, 3, 4, 5} , {2, 3, 4, 5} , {1, 2, 3, 4 , 5}}

Таким образом, мы получаем все 32 подмножества {1, 2, 3, 4, 5}.