Кроме генерации подмножеств данного множества в лексикографическом порядке весьма интересны схемы генерации при которых каждое последующее подмножество отличается от предыдущего вставкой или удалением одного элемента. Первым, естественно, рассмотрим вопрос, связанный с существованием подобных схем. Для этого вначале разберем частные генерации в зависимости от мощности базового множества, затем обобщим их. Считаем, что конкретные подмножества представлены в виде характеристических векторов.
Пусть n - мощность базового множества.
n = 1
1. (0); либо 1. (1);
2. (1). 2. (0).
n = 2
1. (0,0); либо ему симметричный 1. (0,0);
2. (1,0); 2. (0,1);
3. (1,1); 3. (1,1);
4. (0,1). 4. (1,0).
Других вариантов, начинающихся с пустого множества, нет!
n =3
1. (0,0,0,)
2. (1,0,0)
3. (1,1,0)
4. (0,1,0)
5. (0,1,1)
6. (1,1,1)
7. (1,0,1)
8. (0,0,1)
Упражнение. Построить другие варианты генерации подмножеств для n=3,начинающиеся с представления пустого множества.
Обобщим приведенные примеры:
Пусть C1; C2; ...; Ck-1; Ck содержит все k=2n двоичных представлений подмножеств множества из n элементов, причем каждое последующее подмножество отличается от предыдущего вставкой или удалением одного элемента. Тогда последовательность, генерирующая все подмножества множества из n+1 элемента может быть получена, например, так:
Так построенные последовательности двоичных слов являются симметрично отраженными относительно n-ой позиции.
Рассмотрим последовательность номеров изменяемых разрядов при переходе от одного двоичного слово к другому. Обозначим ее Pn. Тогда эта последовательность удовлетворяет следующему рекурсивному определению
P1 = 1; Pn = Pn-1, n, P, n>1.
По индукции легко доказать, что для n>0 Pn = P.
Таким образом последовательность Pn совпадает с ранее определенной последовательностью In.