我问了一个question关于在可变数量的集合中查找没有重复字符的子序列。解决方案是为每对字母创建一个矩阵,丢弃每组中没有出现的字母,然后找到 longest path。在有向无环图中。但是,我不想要最长的路径,我想要几个最长的路径(例如,如果它生成长度为 10、10、9、8、8、3、3、2 和 1 的子序列,我可能想要仅显示前 5 个子序列)。
因此,由于我不只是寻找最长的路径,为了生成结果子序列,而不是使用维基百科文章中描述的最长路径算法,我使用的是一种朴素的算法,它简单地生成一个所有可能的子序列列表。这会生成类似于 an answer 中结果的集合对于我之前的问题。
问题是我想减少它生成的子序列的数量。
例如,如果我有以下集合:
A = AB12034
B = BA01234
C = AB01234
...我的算法目前将得出以下每组中出现的对:
A - 1 B - 1 1 - 2 2 - 3 0 - 3 3 - 4
2 2 3 4 4
3 3 4
4 4
0 0
这在技术上是正确的,但我想消除其中一些对。例如,注意 2
总是在 1
之后.因此,我想消除 A2
和 B2
对(即 A
和 B
不应该直接跳转到 2
...它们应该总是先经过 1
)。另外,1
除了 2
之外,不应该跳转到任何数字, 自 2
总是在它之后立即发生。此外,注意如何 0
总是发生在 B
之间和 3
, 所以我想消除这对 B3
(同样,B
在跳转到 0
之前应该始终经过 3
,因为所有集合都将这三个字母的位置设置为:B < 0 < 3
)。
需要说明的是,当前算法将产生这些子序列:(为简洁起见,我只包括那些以 A
开头的子序列):
A1234
A124 *
A134 *
A14 *
A234 *
A24 *
A34 *
A4 *
A034
A04 *
...以及所有标有 *
的那些应该被淘汰。
生成所需子序列的(正确的)对将是:
A - 1 B - 1 1 - 2 2 - 3 0 - 3 3 - 4
0 0
... 完整的子序列列表将是:
A1234
A034
B1234
B034
1234
234
034
34
换句话说,我试图从这个有向无环图出发:
对此:
我应该使用什么样的算法/逻辑来摆脱这些无关的对(即图形边缘)?或者您认为我首先生成对的逻辑是应该改变的事情吗?
最佳答案
Furthermore, notice how 0 always occurs between B and 3, so I would like to eliminate the pair B3 (again, B should always go through 0 before it jumps to 3, since all sets have the positions of these three letters as: B < 0 < 3).
嗯,好吧,如果n0 < n1 < n2
保留所有集合然后删除所有 (n0, n2)
对?这可以通过以下方式实现(在伪 Python 中):
for(edge in node):
if(len(LongestPath(node, edge.Node)) > 1):
RemovePair(node, edge.Node)
关于javascript - 在尝试寻找最长路径时消除有向无环图中的无关边,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8691834/