从一组偏序中重建一个序列 [英] reconstruct a sequence from a set of partial orders

问题描述

我有一组元素对.这些对中的每对均表示:在最后的顺序中，第一个元素在第二个元素之前. 这对对包含足够多的对，以重建唯一序列.

I have a set of elements pairs. Each one of theses pairs means : In the final sequence the first elements precedes the second element. The set of pairs contains enough pairs to reconstruct a unique sequence.

例如:

如果我的配对对是{(A, B), (A, C), (C, B)}

= A在B 之前， A在C 之前，并且 C在B 之前.

= A precedes B, A precedes C and C precedes B.

我的最终序列是ACB.

现在，我需要一种算法来从这种对对中重建序列. 效率至关重要.欢迎任何聪明的提示！

Now, I need an algorithm to reconstruct sequences from this kind of pair sets. Efficiency is critical. Any smart tip is welcome !

推荐答案

从这些对创建有向图，然后执行

Create a directed graph from those pairs, then perform topological sort.

这篇关于从一组偏序中重建一个序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！