すべての部分注文を列挙する

Question

有限集合のすべての部分注文を効率的に列挙するにはどうすればいいですか？

指定されたプロパティを持つ部分注文が存在するかどうかを確認したいと思います。これをチェックするために、私は小さな有限集合上のすべての可能な部分次数を列挙するために力ずくで行くつもりです。

Answer 1

あなたのプロジェクトが実用的になるためには、それらは本当に小さな有限集合でなければなりません。

N標識posetsの数は、値nは= 18まで知られているスローン配列A001035、ある要素を標識：

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は非標識posetsの数です。驚くことではないが、数字は小さいが、まだ急速に成長している。彼らはn = 16までしか知られていないようです。 P は、上記のリンクOEIS A000112ページの参考文献に記載されているグンナー・ブリンクマンとブレンダン・マッケイによる論文では、アルゴリズムは、あり4483130665195087.

です。この作業は2002年に約200台のワークステーションを使用して行われ、サイズが16のラベルの付いていないポケットの数は約30マシン・年（基準マシンは1 GHz Pentium III）でした。今日では、それは速く行うことができるが、p の値はおそらく約2桁の大きさである。