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

Question

[eatmypants]

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

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

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

Спасибо.

Comments

[Yustas Alexu]

А у Вас какие мысли по этому поводу? Вы хотя бы пытались решить эту задачу?

[eatmypants]

Yuxus: конечно. Я застрял на том, что моё алгоритмическое мышление слишком примитивно. Обычными вложенными циклами мне не удалось решить проблему.

[Yustas Alexu]

Покажите код с вложенными циклами.

[eatmypants]

Yuxus: скажите пожалуйста, какой в нем толк, если он все равно не работает правильно?

Answer 1

[Rsa97]

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

Comments

[eatmypants]

Вы правы, допустил опечатку. Спасибо за ответ.