生成所有大小爲n的預訂/弱訂單的算法

Question

我正在尋找一種中途有效的算法，在給定輸入集的情況下，根據它生成所有全部預訂關係（或等價地，所有弱訂單）。你也可以把它稱爲所有n標記元素的優先安排。

我已經試圖通過首先生成大小爲n的所有排列然後用'〜'摺疊這些排列的子序列來實現這個，但是由於許多重複，這是非常低效的，而且我也遺漏了一些結果。大小由Fubini數字1，1，3，13，75，541，4683，47293，545835，...（OEIS編號A000670）給出，並隨着n的增長而快速增長。我只需要前幾個，比如說，直到n = 8。

示例：對於A = {A，B，C}，其中n = 3的結果是13個預序：

B> A> C，B> A〜C，B> C> A，B〜 c> a，c> b> a，c> a〜b，c> a> b，a〜c> b，a> c> b，a> b〜c，a> b> c，a〜 c，a〜b〜c

Answer 1

不太難。在Python 3中：

import itertools 

def weakorders(A): 
    if not A: # i.e., A is empty 
     yield [] 
     return 
    for k in range(1, len(A) + 1): 
     for B in itertools.combinations(A, k): # i.e., all nonempty subsets B 
      for order in weakorders(set(A) - set(B)): 
       yield [B] + order 

使用例如list(weakorders(range(8)))進行調用。