有关子串序列和顺序的字符串混乱的算法（相同长度，相同字符，独特字符，没有词汇含义的字符串）

Question

假设我有“peachz”作为字符串，“eachzp”和“pahezc”作为尝试用于比较。

我正在寻找一种算法，输出阵列无序的水平，关于事件的相对顺序。 在下面的例子中，我用当前算法来描述问题。我总结了每个角色在原始字符串上的尝试位置的差异。

下面是一个例子图像：
http://i51.tinypic.com/1zz2c10.png http://i51.tinypic.com/1zz2c10.png

“eachzp”具有相同的字符顺序，除了P.由于P具有移动到第一位置中，每隔一个字符被看作是一个位置出的地方。 “eachzp”将输出10的无序度，而完全混杂的“pahezc”尝试将输出8。这是不正确的。 Hamming或Levenshtein距离等事情也不会考虑这些“顺序序列”。

我的问题是： 有没有一种算法可以用来输出字符串的无序/相似性，考虑到它们的字符的相对顺序？

（这应该是没有字典相关，因为字符串是不言而没有任何词汇意义。如果有帮助，人物会也将在每个字符串是唯一的。）

TIA

/编辑：我会尽力解释以不同的方式我的情况后，试图进一步细节吧：

• 中的字符串始终是相同长度的

• 字符串总是有相同的字符（例如。如果原始文件是“ors”，其他字符串只能是“ors”，“osr”，“sor”，“ros”，“sro”或“rso” - 长度和字符相同）

• chars总是在每串

• 的字符串唯一不是的话，并有在所有

• 我需要的算法取序考虑没有词义。如果原始字符串是“peachz”，则“eachzp”的排列方式几乎完全相同 - 只有“p”不合适。这应该更类似于“peachz”而不是“pahezc”，它更加混乱，并且在所有方向上（我觉得这个“方向”概念可能与解决方案相关）。

• “eapchz”也应该比“eachzp”更少乱码。在这两种情况下，只有字母“p”不合适，但它在“eapchz”上移动了较短的距离。

所有帮助表示赞赏。谢谢

Answer 1

编辑：完全新算法。

在我看来，你似乎“无序”的概念对应于与原始文件相比，杂乱字符串的可读性如何。可读性的体面度量将是找到未加扰的子字符串，然后查看子字符串的总体顺序是什么。

1. 查找所有匹配原始字符串的最大长度扰码字符串的子字符串，并将它们按照找到的顺序存储在数组中。注意：由于每个字母只出现一次，子字符串将不相交。
2. 设“碎片分数”为最大子串数。
3. 设“连续性得分”为子串长度的平方和。
4. 对于每个子字符串，通过将其与子字符串的整体顺序进行比较来对它进行评分（加起来应该有多少，以及它应该多少之后）。让字符串的“订单分数”为所有子字符串分数的总和。
5. 我们现在有一个三维评分。比较字符串首先比较碎片评分，如果他们是平等比较连续性评分，如果他们是相等比较秩序评分。较低的碎片分数较少扰乱，较高的连续性和顺序分数较少混乱。

例： “acpehz” 具有FRAG，CONT，和顺序得分3，图12，4.

通过这种方法，我们有 “peachz” < “eachzp” < “pahezc”，如所期望。

我能想到的这个算法的唯一明显限制是，它可能会非常慢，“eachzp”比“pezach”更不争抢，即使你可能认为它们是平等的，因为“只有一个字母是无序“。

Answer 2

这听起来像是一个数组中的counting inversions问题;在链接中，您可以找到类似mergesort的O（n log n）分治算法的描述。

在反演问题中，你有一个像1 3 2 5 4这样的数组，并且想要测量它与1 2 3 4 5相比的失序程度。所以1 2 3 4 5是模拟你的“ peachz“，如果我们将1分配给'p'，将2分配给'e'等，他们是同样的问题。倒置是任何一对失序的元素（不一定是相邻的元素）。

这是可能的，你想比反转次数等措施 - 我最好的猜测是旋转计数，其中一个旋转从一个位置删除元素，坚持它在其他地方。例如，“eachzp”离“peachz”只有一圈。我认为你可以用O（n^2）动态编程算法来计算旋转，比如Levenshtein距离，但我没有检查过这个..

Answer 3

如果我正确理解你的问题，你正在寻找Kendall -Tau距离度量。你可以阅读关于它here。