Алгоритм генерации всех подмножеств

, требуется определить количество всех подмножеств и сгенерировать их. Множество всех подмножеств включает и содержит . Каждое подмножество будем кодировать набором из 0 и 1. Если на - ом тесте стоит 1, значит входит в подмножество, если 0, то не входит.

По любому такому набору можно однозначно определить подмножество, подмножеств будет столько, сколько наборов длины из 0 и 1. Количество подмножеств .

Сгенерируем все наборы из 0 и 1. Для генерации можно использовать двоичное представление всех целых чисел от 0 до . Иногда требуется, чтобы соседние подмножества как можно меньше отличались друг от друга своим составом. Будем использовать код Грея.

Код Грея получают из двоичного представления следующим образом:

1. Берем двоичное представление числа

2. Запишем число со сдвигом на одну позицию вправо

3. В каждой позиции производится сложение по модулю 2

Дата добавления: 2014-01-07