Jak skutecznie wyliczyć wszystkie częściowe zamówienia na skończonym zestawie?Wyliczyć wszystkie częściowe zamówienia
Chcę sprawdzić, czy istnieje zamówienie częściowe o określonych właściwościach. Aby to sprawdzić, używam brutalnej siły, aby wyliczyć wszystkie możliwe częściowe rozkazy na małych skończonych zestawach.
Będą musiały być naprawdę małymi skończonymi zestawami, aby projekt był praktyczny.
Liczba znakowanych Posets gdzie n oznakowanych elementów jest sekwencja A001035 Sloane, których wartości są znane do 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
Sekwencja A000112 oznacza liczbę oznakowanych Posets; nic dziwnego, że liczby są mniejsze, ale wciąż szybko rosną poza zasięgiem. Wydają się znani tylko do n = 16; P jest 4483130665195087.
Jest algorytm papieru Gunnar Brinkman i Brendan McKay, wymieniono w odnośnikach na OEIS A000112 stronie połączone powyżej. Prace zostały wykonane w 2002 roku, z wykorzystaniem około 200 stacji roboczych, a zliczanie 4483130665195087 nieznakowanych poserów o rozmiarze 16 trwało około 30 maszyn-lat (maszyna referencyjna to Pentium III 1 GHz). Dzisiaj można to zrobić szybciej, ale wtedy wartość p jest przypuszczalnie większa o dwa dziesiętne rzędy wielkości.
Nie nastąpi. Istnieje wiele wykładniczo. –
powiązane: http://math.stackexchange.com/questions/232613/how-many-partial-order-on-an-set –
@ G.Bach- Nawet jeśli istnieje wykładniczo wiele obiektów, wciąż można wyliczyć wszystkie im. To może trochę potrwać. – templatetypedef