有關子串序列和順序的字符串混亂的算法（相同長度，相同字符，獨特字符，沒有詞彙含義的字符串）

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。