Задать вопрос
@eatmypants
алгоритмы

Как пройти все подмножества в множестве?

Здравствуйте,

Есть множество объектов. К примеру: {A,B,C}. Нужно найти все подмножества множества {A,B,C} через циклы. Как лучше это сделать? Сложность алгоритма должна быть O(2^n). Ж

Желательно пример на java, но можно и на другом любом языке.

Спасибо.
  • Вопрос задан
  • 4494 просмотра
4 комментария
Подписаться 3 Оценить 4 комментария
Пригласить эксперта
Ответы на вопрос 1
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Вообще-то у n-элементного множества 2n подмножеств, так что n2 при n > 2 получить нереально.
Один из алгоритмов перечисления:
1. Заводим второй массив (булеан), того же размера, что и исходный, инициализируем его нулями.
2. Выводим подмножество из тех элементов исходного массива, которым в булеане соответствуют единицы.
3. Трактуя булеан как запись числа в двоичной системе прибавляем к нему 1.
4. Если в булеане есть хоть одна 1, переходим к пункту 2.
Ответ написан
1 комментарий
1 комментарий
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Вакансии с Хабр Карьеры
С developer (алгоритмист)
СберТех • Москва
от 350 000 ₽
Бэкенд программист
Grade Factor • Москва
от 80 000 ₽
С++ developer
TQB - хай-тек рекрутмент по-хардкору • Москва
от 300 000 ₽
Ещё вакансии
Заказы с Хабр Фриланса
Разработка VST-плагина
19 апр. 2024, в 20:43
20000 руб./за проект
Нарисовать баннер для интернет-магазина
19 апр. 2024, в 20:35
500 руб./в час
Разработать несистемный алерт
19 апр. 2024, в 20:11
500 руб./за проект
Ещё заказы