Перечислить все частичные заказы

Как эффективно перечислить все частичные порядки на конечном множестве?

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


algorithm math discrete-mathematics poset
person porton    schedule 22.04.2013    source источник
comment
Не случится. Их экспоненциально много.   -  person G. Bach    schedule 23.04.2013
comment
связанные: math.stackexchange .com/questions/232613/   -  person Ray Tayek    schedule 23.04.2013
comment
@ G.Bach- Даже если объектов экспоненциально много, вы все равно можете перечислить их все. Просто это может занять некоторое время.   -  person templatetypedef    schedule 23.04.2013
comment
@templatetypedef Он попросил об эффективности; насколько я знаю, это обычно относится к полиномиальному общему времени выполнения.   -  person G. Bach    schedule 23.04.2013
comment
@ G.Bach- Я полагаю, это правда. Однако вы можете подумать о том, чтобы попытаться эффективно сгенерировать комбинаторно множество элементов, сказав, что эффективность означает полиномиальные накладные расходы для каждого элемента.   -  person templatetypedef    schedule 23.04.2013
comment
@templatetypedef Я думаю, это будет концепция, известная как полиномиальная задержка?   -  person G. Bach    schedule 23.04.2013
comment
Интересно, что поиск Google по этому вопросу, похоже, не дает ничего. Кнут, том 4A, кажется, не охватывает этого, и не похоже, что это планируется в какой-либо другой части или в томе 4. Это кажется мне проблемой, которая должна была решаться раньше, но Я не могу найти никаких доказательств этого. Я надеюсь, что кто-то знает, как это сделать!   -  person templatetypedef    schedule 23.04.2013
comment
Это может помочь узнать, какие свойства вы хотите удовлетворить. Если они хороши, они могут ограничить ваш поиск подпространством полиномиального размера.   -  person torquestomp    schedule 23.04.2013
comment
Я не очень разбираюсь в посетах, но будет ли этот пример правильным перечислением? (Haskell GHCi): Prelude Data.List> concatMap permutations . subsequences $ ["x","y","z"], который будет перечислять: [[],["x"],["y"],["x","y"],["y","x"],["z"],["x","z"],["z","x"],["y","z"],["z","y"],["x","y","z"],["y","x","z"],["z","y","x"],["y","z","x"],["z","x","y"],["x","z","y"]]   -  person גלעד ברקן    schedule 23.04.2013
comment
@groovy Posets — это наборы вместе с отношениями, то есть подмножества YxY для некоторого множества Y. Таким образом, для [x, y, z] все posets потребуют подмножества [x, y, z]² в качестве отношения частичного упорядочения.   -  person G. Bach    schedule 23.04.2013
comment
@ G.Bach Понятно ... это не так просто. Я думаю, что это может быть статья, на которую Ричи ссылается в своем ответе: cs.anu .edu.au/~bdm/papers/posets.pdf   -  person גלעד ברקן    schedule 23.04.2013
comment
@porton Я предлагаю вам рассказать нам немного больше о том, что вы пытаетесь сделать.   -  person mitchus    schedule 23.04.2013
comment
@groovy- Можете ли вы опубликовать это как ответ? Это в значительной степени идеальный ресурс для ответа на этот вопрос.   -  person templatetypedef    schedule 05.05.2013

Ответы (1)


arrow_upward
12
arrow_downward

Они должны быть очень маленькими конечными наборами, чтобы ваш проект был практичным.

Количество помеченных множеств с n помеченными элементами представляет собой последовательность Слоана A001035, значения которой известны до n=18:

0 1
1 1
2 3
3 19
4 219
5 4231
6 130023
7 6129859
8 431723379
9 44511042511
10 6611065248783
11 1396281677105899
12 414864951055853499
13 171850728381587059351
14 98484324257128207032183
15 77567171020440688353049939
16 83480529785490157813844256579
17 122152541250295322862941281269151
18 241939392597201176602897820148085023

Последовательность A000112 — это количество непомеченных наборов; неудивительно, что цифры меньше, но все равно быстро растут за пределами досягаемости. Кажется, они известны только до n=16; p16 равно 4483130665195087.

В статье Гуннара Бринкмана и Брендана Маккея есть алгоритм, указанный в ссылках на странице OEIS A000112, ссылка на которую приведена выше. Работа была выполнена в 2002 году с использованием около 200 рабочих станций, а подсчет 4483130665195087 непомеченных наборов poses размером 16 занял около 30 машино-лет (эталонной машиной является Pentium III с тактовой частотой 1 ГГц). Сегодня это можно было бы сделать быстрее, но тогда значение p17 предположительно будет примерно на два десятичных порядка больше.

person rici    schedule 22.04.2013