Комбинаторика. Найти количество возможных перестановок

[Arthur88]

Нужно найти количество возможных перестановок для множества, имея правила следования элементов.
Пример.
1) Задача:
имеем множество { a,b,c,d } и правила к нему { a>b, c>d }.
Решение:
количество возможных перестановок 4!=24,
правило a>b "отсекает" половину возможных перестановок 24/2=12 (перестановок),
правило c>d "отсекает" оставшеюся часть 12/2=6(перестановок).
Ответ: 6 перестановок.
2) Задача:
имеем множество { a,b,c,d,e } и правила к нему { a>b, b>c, c>d }.
Решение:
количество возможных перестановок 5!=120,
правило a>b "отсекает" половину возможных перестановок 1/2, 120*(1/2)=60(перестановок),
правило b>c "отсекает" 1/3 от оставшихся перестановок 60*(1/3)=20 (перестановок),
правило c>d "отсекает" 1/4 от оставшихся перестановок 20*(1/4)=5 (перестановок).
Ответ: 5 перестановок.

Вывод:
для правил которые не содержат одинаковых элементов { a>b, c>d, e>f } происходит деление на 2 для
каждого правила (задача №1),
для правил которые имеют вид { a>b, b>c, c>d, d>e } происходит деление на 2, 3, 4, 5 и т.д. (задача №2),
для правил которые имеют вид { a>b, a>c, a>d, a>e } происходит умножение на дробь 1/2, 2/3, 3/4, 4/5 и т.д.

Это все то, что я смог найти экспериментальным путем. Совершенно не понятно, какая закономерноть для "смешенных правил" { a>b, a>c, e<d, c>e, b>e .. } множества могут иметь разное кол. элементов и правила могут быть самые разные. причем правило { a>b, b>c } можно раскрыть как { a>b, a>c, b>c }.

Помогите плиз. или тыкнети меня в литературу, где возможно найти ответ.
Искал по википедий нашел такие понятия как: "частично упорядоченное множество", "гуппы", "решетки".
Но что начать изучать и даст ли это ответ на мою задачу, я не знаю:(

Заранее Спасибо.

[zxvenom]

Это ты сам разбирал? Нутыкрууут!

Твои две задачи можно решить и не извращаясь так. Первая - это разбиение на два подмножества \( {4 \choose 2,\ 2} = \frac{4!}{2!\ 2!} = 6 \), вторая -  \( {5 \choose 4,\ 1} = \frac{5!}{4!\ 1!} = 5 \) . Посмотри на статьи Разбиение множества и Мультиномиальный коэффициент на википедии.

Метод решения интересный, канешна, но вроде кажется наверно похоже подобные перестановки надо все искать через размещения и сочетания.
Ну или можно таки попробовать сначала все "смешанные" правила к одному виду привести (только "<" например), затем попытаться найти несовпадения вроде a<b, b<c, c<a, и если не повезло и таких несовпадений нет, то... ... ... .. .. . То решать через размещения и сочетания, да...

Короче жди нормального ответа от других, вот %/

[Arthur88]

Это ты сам разбирал? Нутыкрууут!

не считаю себя крутым.

можно таки попробовать сначала все "смешанные" правила к одному виду привести (только "<" например)

считай что все правила содержат "<" по умолчанию - приводить ничего не нужно.

попытаться найти несовпадения вроде a<b, b<c, c<a

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

Большое спасибо за помощь! обязательно прочитаю статьи.

Вот недавно пришла мысль построить граф и отразить на нем все возможные сочетания без повторений. Имея такой граф задача сводится только к подсчету кол. путей от начала графа до его конца.
Разъясню на примере. что я за бурду написал:)
множество { a,b,c }, правило { a>b, a>c }, теперь стоим граф с вершинами { begin, a, b, c, ab, ac, bc, abc } и ребра { ( begin,a ), ( a,ab ), (a,ac), ( ab,abc ), ( ac,abc ) } begin -вершина графа.
Но, метод достаточно сложный в реализаций.
 1-найти все вершины, 2-найти все его ребра, 3-подсчитать все возможные пути.

Спасибо.

[Arthur88]

если кто-то знает решение более эффективное, чем стоить граф.
плиз. помогите

[zxvenom]

Я бы на твоём месте просто перебрал все варианты...

Если здесь не ответят, загляни на dxdy.ru и eek.diary.ru

Когда напишешь прогу, запости сюда, ладно? Мне самому интересно стало.