Генерация подмножеств за счет их минимального изменения.

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

Пусть 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 элемента может быть получена, например, так:

С10; C20; ...; CK-10; CK0; CK1; CK-11; ....;C21; C11.

Пример n=4

Так построенные последовательности двоичных слов являются симметрично отраженными относительно n-ой позиции.

Рассмотрим последовательность номеров изменяемых разрядов при переходе от одного двоичного слово к другому. Обозначим ее Pn. Тогда эта последовательность удовлетворяет следующему рекурсивному определению

P1 = 1; Pn = Pn-1, n, P , n>1.

По индукции легко доказать, что для n>0 Pn = P .

 

Таким образом последовательность Pn совпадает с ранее определенной последовательностью In.

Пример. n = 4, P4 = I4 = 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1.

Заметим, что значение m, 1£m£n, первый раз встречается как 2m-1-ый член Pn, затем повторяется через каждые 2m-1 членов последовательности.

Учитывая сказанное, можно построить на языке Паскаль следующий рекурсивный алгоритм:

program SET2 (,output);

const n= ;

var s : array [1..n] of 0..1;

i : integer;

procedure GRAY (m : integer);

begin

if m=0 then

begin

{1} for i:=1 to n do write( s[i] ); writeln;

end

else

begin

{2} GRAY (m-1);

{3} s[m]:=1-s[m];








Дата добавления: 2015-08-11; просмотров: 805;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.006 сек.