可逆排列算法

Question

列表排列的哪個算法是可預測的？

例如，我可以得到的排列

（Haskell代碼）

--List of all possible permutations 
permut [] = [[]] 
permut xs = [x:ys|x<-xs,ys<-permut (delete x xs)] 

--In command line call: 
> permut "abc" !! 2 
"bac" 

數第i個，但我不知道如何扭轉這種局面。 我想Ø是這樣的：

> getNumOfPermut "abc" "bac" 
2 

任何可逆算法去！ 提前謝謝！

Answer 1

好吧，我我希望等到你回答了我的問題，但是我非常有趣地找出答案，我只需要將它寫出來並分享。書呆子狙擊，我想！我確信我不是第一個發明了下面算法的人，但我希望你喜歡這個演講。

我們的第一步是給出permut（您還沒有完成）的實際可運行實現。我們的實現策略將是一個簡單的實現策略：選擇列表中的某個元素，選擇其餘元素的一些排列，並將它們連接起來。

chooseFrom [] = [] 
chooseFrom (x:xs) = (x,xs) : [(y, x:ys) | (y, ys) <- chooseFrom xs] 

permut [] = [[]] 
permut xs = do 
    (element, remaining) <- chooseFrom xs 
    permutation <- permut remaining 
    return (element:permutation) 

如果我們的樣本名單上運行此，這是很清楚它的行爲：

> permut [1..4] 
[[0,1,2,3],[0,1,3,2],[0,2,1,3],[0,2,3,1],[0,3,1,2],[0,3,2,1],[1,0,2,3],[1,0,3,2],[1,2,0,3],[1,2,3,0],[1,3,0,2],[1,3,2,0],[2,0,1,3],[2,0,3,1],[2,1,0,3],[2,1,3,0],[2,3,0,1],[2,3,1,0],[3,0,1,2],[3,0,2,1],[3,1,0,2],[3,1,2,0],[3,2,0,1],[3,2,1,0]] 

結果有很多結構;例如，如果我們通過組所包含的列表中的第一個元素，有四個組，每組包含6（其爲3！）元素：

> mapM_ print $ groupBy ((==) `on` head) it 
[[0,1,2,3],[0,1,3,2],[0,2,1,3],[0,2,3,1],[0,3,1,2],[0,3,2,1]] 
[[1,0,2,3],[1,0,3,2],[1,2,0,3],[1,2,3,0],[1,3,0,2],[1,3,2,0]] 
[[2,0,1,3],[2,0,3,1],[2,1,0,3],[2,1,3,0],[2,3,0,1],[2,3,1,0]] 
[[3,0,1,2],[3,0,2,1],[3,1,0,2],[3,1,2,0],[3,2,0,1],[3,2,1,0]] 

所以！列表的第一位數字告訴我們「要添加多少個6」。此外，上述分組中的每個列表都表現出相似的結構：第一組中的列表有三組，每組兩列！作爲它們的第二個元素，每個包含1,2和3;這些組中的每個列表都有2個1的組！每個元素從每個剩餘數字開始;並且每個那些組有1個0組！每個元素都以唯一的剩餘數字開始。所以第二位數字告訴我們「添加多少個2」​​，第三位數字告訴我們「添加多少個1」，最後一位數字告訴我們「添加多少個1」（但總是告訴我們添加0 1） 。

如果您之前在數字上實現了基數改變功能（例如，十進制到十六進制或類似的），您可能會認識到這種模式。事實上，我們可以把它看作是一個滑動基礎的基礎變化操作：而不是1s，10s，100s，1000s等等列，我們有0！s，1！s，2！s，3！ s，4！s等欄目。我們來寫吧！爲了提高效率，我們將使用factorials函數預先計算所有滑動基準。

import Data.List 

factorials n = scanr (*) 1 [n,n-1..1] 
deleteAt i xs = case splitAt i xs of (b, e) -> b ++ drop 1 e 

permutIndices permutation original 
    = go (factorials (length permutation - 1)) 
     permutation 
     original 
    where 
    go _ [] [] = [0] 
    go _ [] _ = [] 
    go _ _ [] = [] 
    go (base:bases) (x:xs) ys = do 
     i <- elemIndices x ys 
     remainder <- go bases xs (deleteAt i ys) 
     return (i*base + remainder) 
    go [] _ _ = error "the impossible happened!" 

這裏有一個樣本完整性檢查：

> map (`permutIndices` [1..4]) (permut [1..4]) 
[[0],[1],[2],[3],[4],[5],[6],[7],[8],[9],[10],[11],[12],[13],[14],[15],[16],[17],[18],[19],[20],[21],[22],[23]] 

而且，爲了好玩，在這裏你可以看到其正確處理歧義：

> permutIndices "acbba" "aabbc" 
[21,23,45,47] 
> map (permut "aabbc"!!) it 
["acbba","acbba","acbba","acbba"] 

...並表明這是顯著比elemIndices更高效：

> :set +s 
> elemIndices "zyxwvutsr" (permut "rstuvwxyz") 
[362879] 
(2.65 secs, 1288004848 bytes) 
> permutIndices "zyxwvutsr" "rstuvwxyz" 
[362879] 
(0.00 secs, 1030304 bytes) 

分配/時間少於千分之一。看起來像一場勝利！

Answer 2

所以，要清楚，你正在尋找一種方式來找到在給定的permutions-

["abc", "acb", "bac", ....] 

這個問題實際上有一個列表的給定permution-

"bac" 

位置沒有什麼本質上與批准本身有關。您想要查找數組中元素的位置。

由於@raymonad在他的評論中提到，stackoverflow.com/questions/20641772/處理這個問題，並且有答案，使用elemIndex。

elemIndex thePermutionToFind $ permut theString 

請記住，如果字母重複，一個值可能會出現一次以上的輸出，如果你的「PERMUT」功能不會刪除這些重複（即 - 請注意，PERMUT「AA」 = [ 「aa」，「aa」]）....在這種情況下，elemIndices函數將有用。

如果elemIndex返回Nothing，這意味着您提供的字符串不是一個permution。

（這不是大串的最effecient算法，因爲permutions數量的增長，如串....這是比指數更差的大小的階乘）。