Come enumerare in modo efficiente tutti gli ordini parziali su un insieme finito?Enumera tutti gli ordini parziali
Voglio verificare se esiste un ordine parziale con proprietà specificate. Per verificarlo, procedo con la forza bruta per enumerare tutti i possibili ordini parziali su insiemi piccoli finiti.
Saranno davvero dei piccoli set finiti affinché il tuo progetto sia pratico.
Il numero di posets marcati con n elementi con etichetta è sequenza Sloane A001035, i cui valori sono noti fino ad 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
Sequence A000112 è il numero di posets etichettati; Non sorprendentemente, i numeri sono più piccoli ma continuano a crescere rapidamente fuori dalla portata. Sembrano essere noti solo fino a n = 16; p è 4483130665195087.
C'è un algoritmo in un articolo di Gunnar Brinkman e Brendan McKay, elencato nei riferimenti sul OEIS A000112 pagina linkata sopra. Il lavoro è stato svolto nel 2002, utilizzando circa 200 postazioni di lavoro e il conteggio dei 4483130665195087 posteri non etichettati di dimensione 16 ha richiesto circa 30 anni macchina (la macchina di riferimento è un Pentium III da 1 GHz). Oggi, potrebbe essere fatto più velocemente, ma il valore di p è presumibilmente di circa due ordini decimali di grandezza maggiore.
Non succederà. Ci sono molti esponenzialmente. –
correlati: http://math.stackexchange.com/questions/232613/how-many-partial-order-on-an-set –
@ G.Bach- Anche se ci sono molti oggetti in modo esponenziale, è comunque possibile enumerare tutti loro. Potrebbe volerci un po 'di tempo. – templatetypedef