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

Question

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

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

Answer 1

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

Число меченых ч.у.м. с п меченых элементов последовательности Sloane A001035, значения которых известны до п = 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; р является 4483130665195087.

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