给定一个成对排序矩阵,如何枚举所有可能的总排序

基于来自不同答案的评论流,我提出以下算法:

1. 使用 connected components 算法。该算法包括一个简单的深度优先(或广度优先)搜索,其中只考虑头小于其尾部的链接。(也就是说,您只关注链接 i -> j i < j Pairwise[i][j] == 0 || Pairwise[j][j] == 0 . 每个组件都标有组件中任何元素的最小索引(通常称为“代表”)。这个步骤的输出是从索引到代表的映射,这是一个简单的向量。

2. 通过将两个组件之间的所有“小于”项折叠到一个组件之间的关系中,构造一个简化图。

3. transitive closure 在简化图上,进行深度优先扫描 循环检测 topogical sort .

i 是元素的直接前身 j 如果 Pairwise[i][j] = 1 . 只需运行搜索算法(很可能是深度优先搜索)即可枚举所有路径。
忽略 -1 1 其他地方的价值。
如果在总排序中包含等式(通过处理 0 价值观 1. s) ,您将有无限多个路径,因此忽略 那也是。