假设我有一堆字符串对，代表“之前”和“之后”的值。举个简单的例子:
aaaabbbb -> aabbbbaa
abbbbbbb -> bbbbbbab
aaabbbaa -> abbbaaaa
cccccccc -> cccccccc
我如何确定一种可能的排列可能是 [ 6, 7, 0, 1, 2, 3, 4, 5 ]，或者换句话说，所有字符都向左旋转了两个空格？
关于这个问题有一些文献吗？此外，如果列表中的某些对不完全匹配，是否会有“最可能”排列的概念？除了左右移动之外，还能找到更复杂的排列吗？
最佳答案
你需要了解graph theory的基本概念和 matching .
假设 before 的每个位置都是左节点，after 的每个位置都是右节点。
对于左位置 i 和右位置 j，连接一条边从左节点 i 到右节点 j，当且仅当 x[i] 在所有对 x -> y 中等于 y[j]。
那么问题就变成了找到这个二部图的完美匹配，这是一个已解决的问题。
“最有可能”排列会更难，它需要“最有可能”的确切定义。您想满足尽可能多的对吗？还是更多匹配的字符是首选？
关于algorithm - 从字符串对中查找未知排列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42127560/