假设我们有一组字母,例如{A,B,C,D,E,F} 我们要按顺序排列,受一组规则约束。
我们不知道序列是什么样的,但我们知道序列中有哪些字母。我们有关于字母对排序的信息。是否有任何众所周知的算法或方法可以找到满足给定信息的可能序列?
例如,假设我们有以下信息:
- 序列中有6个字母{A,B,C,D,E,F}
- E在B之后
- C在E之后
- A在D之后
- F在B之后
- D在E之后
满足这些条件的可能序列是什么?
最佳答案
构建有向图G(V,E)
V = {a,b,c,d,e}
你的字母
对于 x 在 y 之前的任何对,E = (x,y)。
然后使用拓扑排序(read more here)(visualization here)
关于algorithm - 一种基于有限信息的序列生成算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37331004/