Тема 3. Генерация подмножеств множества

Begin

for j:= 1 to n do write (p[j]); writeln;

i:=n;

while p[ r[i]+d[i] ] > i do

begin

{*} d[i]:=-d[i]; i:=i-1 {поиск перемещаемого элемента}

end;

k:=r[i]; t:=k+d[i];

j:=p[t]; p[k]:=j; p[t]:=i; {транспозиция элементов}

r[i]:=r[j]; r[j]:=k {корректировка обратной перестановки}

end

end.

Упражнения. 1. Доказать, что условием окончания генерирования всех перестановок является то, что перемещаемым становиться элемент 1.

2. Показать, что операторы строки {*} выполняются раз. Определить временную вычислительную сложность алгоритма. Какова его емкостная вычислительная сложность?

3. Написать программу, которая генерирует перестановки с помощью одной транспозиции соседних элементов и при n=4 выдает следующую последовательность:

1. <1 2 3 4> 7. <3 1 2 4> 13. <4 3 2 1> 19. <4 2 1 3>

2. <2 1 3 4> 8. <1 3 2 4> 14. <4 3 1 2> 20. <4 2 3 1>

3. <2 3 1 4> 9. <1 3 4 2> 15. <4 1 3 2> 21. <2 4 3 1>

4. <2 3 4 1> 10. <3 1 4 2> 16. <1 4 3 2> 22. <2 4 1 3>

5. <3 2 4 1> 11. <3 4 1 2> 17. <1 4 2 3> 23. <2 1 4 3>

6. <3 2 1 4> 12. <3 4 2 1> 18. <4 1 2 3> 24. <1 2 4 3>.

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

При программировании на языке Паскаль возможны два подхода к представлению подмножеств конечного множества. В первом, основанном на использовании структурного типа SET OF, базовый тип (элементы множества) задается некоторым простым типом. При этом пользователь может давать имена элементам множества, определять их упорядоченность и применять операции, допустимые над множествами языка Паскаль. Второй подход основан на том, что пользователь интерпретирует множества с помощью других типов, чаще всего массивов. В этом случае, элементы множества трактуются как элементы массива, они могут считаться как упорядоченные, например, по упорядоченности индекса, а выполняемые над ними операции определяются применяемыми операторами или процедурами. Возможна также интерпретация множеств в виде списочных структур. Отметим, что второй подход естественен, когда по условию программируемой задачи элементы сами по себе имеют сложную структуру.

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

Для того чтобы более точно описать проблемы, возникающие в нижеописанных алгоритмах, будем считать, что базовое множество содержит n элементов, а каждое конкретное его подмножество представляется в виде массива. При этом i-й элемент массива принимает значение 1, если i-й базовый элемент (1 £ i £ n) принадлежит множеству, и нулю в противном случае (сравните с понятием характеристической функции множества, используемое в математике). Кроме того, считаем, что упорядоченность элементов множества соответствует упорядоченности индексов массива. Будем изображать множества в виде кортежей из n нулей и единиц.

Пример. X=(1,0,0,0,1,1) означает, что базовое множество содержит шесть упорядоченных элементов, а в множество X включены первый, пятый и шестой по порядку элементы. Пустое множество в этом случае представляется (0,0,0,0,0,0), а множество всех элементов (1,1,1,1,1,1).

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

Дата добавления: 2013-12-11