Немного комбинаторики
Добавлено: 05 окт 2009, 07:41
Есть некоторая последовательность узлов
A также множество пар
Данные пары определяют "вложенность" узлов, т.e пара
говорит o том, что узел
вложен в узел
Фактически B - это ориентированный граф узлов. Вложенность при этом транзивна, т.e если A вложено в B a B вложено в C то A вложено в C
Назовем две последовательности
эквивалентными, если после выкидывания из каждого множества всех вложенных узлов данные множества совпадают
Составляется множество C которое удовлетворяет следующим условиям:
1. Оно является подмножеством булеана A_n (тоесть подмножеством множества всех подмножеств)
2. B данном множестве нет двух эквивалентных элементов
Необходимо выяснить
1. Сколько элементов содержит C
2. Построить эффективный алгоритм генерации множества C
Задача навеяна Этим
A также множество пар
Данные пары определяют "вложенность" узлов, т.e пара
говорит o том, что узел
вложен в узел
Фактически B - это ориентированный граф узлов. Вложенность при этом транзивна, т.e если A вложено в B a B вложено в C то A вложено в C
Назовем две последовательности
эквивалентными, если после выкидывания из каждого множества всех вложенных узлов данные множества совпадают
Составляется множество C которое удовлетворяет следующим условиям:
1. Оно является подмножеством булеана A_n (тоесть подмножеством множества всех подмножеств)
2. B данном множестве нет двух эквивалентных элементов
Необходимо выяснить
1. Сколько элементов содержит C
2. Построить эффективный алгоритм генерации множества C
Задача навеяна Этим