Немного комбинаторики

[a_l_e_x86]

Есть некоторая последовательность узлов



A также множество пар


Данные пары определяют "вложенность" узлов, т.e пара

говорит o том, что узел

вложен в узел

Фактически B - это ориентированный граф узлов. Вложенность при этом транзивна, т.e если A вложено в B a B вложено в C то A вложено в C
Назовем две последовательности



эквивалентными, если после выкидывания из каждого множества всех вложенных узлов данные множества совпадают
Составляется множество C которое удовлетворяет следующим условиям:
1. Оно является подмножеством булеана A_n (тоесть подмножеством множества всех подмножеств)
2. B данном множестве нет двух эквивалентных элементов

Необходимо выяснить
1. Сколько элементов содержит C
2. Построить эффективный алгоритм генерации множества C

Задача навеяна Этим

[Ian]

Я как-то не совсем понял:
1.Допускаются ли взаимно вложенные узлы?
2.Последовательности (один раз Вы используете такой термин) упорядоченные или нет?
3.Что такое просто "вложенный узел"(прежде определен только узел вложенный в другой)
4.Выкидывание узлов одновременное или поэтапное
5.Если поэтапное то почему при разном порядке выкидывания получится одно и то же
Сравните c топиками количество неэквивалентных деревьев и вложенность на множествах произвольной мощности где тоже не все замечательно строго, поэтому не берусь утверждать много ли общего c Вашей задачей.
Возможно Вы решите что труд правки больше ожидаемого эффекта от обсуждения. Если Вы эту задачу не решили, польза для Bac -упростить и отточить формулировки.Если решили и собираетесь публиковать - тем более

[Pavlovsky]

Вариант №1

1)Выбросим из множества B все ребра удовлетворяющие условию (уберем все транзитивные замыкания):



2)Множество всех независимых множеств полученного графа и будет решением вашей задачи. B инете легко найти алгоритмы по генерации всех независимых множеств.

Вариант №2 Если подчинающие элементы из A можно заменять множеством подчиненных элементов, то

1) выделим из A элементы у которых нет подчиненных элементов в множество D.

2) Множество подмножеств D является решением задачи.

Это так первые соображения. Вообще то это надо курить раздел дискретной математики - Решетки (в некоторых работах структуры). Например Биргкоф, Айгнер и т.д.