我必須撰寫一個 Haskell 函式來給出給定串列的所有可能排列。
型別簽名必須是：
permutations :: [a] -> [[a]]
例如，可接受的結果是（在 下ghci）：
λ>
λ> permutations [1,2,3]
[[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]]
λ>
以下限制適用：
- 普通串列是唯一授權的資料結構，因此沒有
Set或Vector. - 排列可以按任何順序產生。
- 該函式必須適用于任何元素型別，即無
Ord a或Eq a實體。 - 只能使用標準 Prelude 中的庫函式。
有誰知道我該怎么做？
uj5u.com熱心網友回復：
有幾種方法可以解決這個問題。jpmarinier 在評論中提出了一種可能的方法，但我認為遵循輸入串列結構的遞回方法在 Haskell 中更自然。
對于這種遞回方法，您必須實作在串列為空的情況下需要發生的事情以及在串列包含至少一個元素的情況下需要發生的事情，在這種情況下，您還可以在其余部分遞回使用該函式串列。一般結構為：
permutations [] = _
permutations (x:xs) = let xs' = permutations xs in _
空串列的情況非常簡單，但是有一些不同的選擇可以讓編譯器滿意，因此可能不會立即清楚您應該選擇哪一個。
對于至少有一個元素的情況，我將使用第二個輔助函式splits :: [Int] -> [([Int],[Int])]，該函式將輸入串列的所有可能拆分計算為兩個串列。
這是一個示例輸入和輸出，可能會使我的意思更清楚：
splits [1,2,3] == [([],[1,2,3]),([1],[2,3]),([1,2],[3]),([1,2,3],[])]
此函式的實作也是遞回的，并遵循相同的模式：
splits [] = _
splits (x:xs) = let xs' = splits xs in _
uj5u.com熱心網友回復：
在上排列維基百科的文章使我們，在許多其他事情時，斯坦豪斯-約翰遜-Trotter的演算法，這似乎非常適合鏈表。
對于這個演算法，一個基本的構建塊是一個我們可以宣告為的函式：
spread :: a -> [a] -> [[a]]
例如，運算式spread 4 [1,2,3]必須將 4 放在 [1,2;3] 內的所有可能位置，因此計算結果為：[[4,1,2,3],[1,4,2,3],[1,2,4,3],[1,2,3,4]]。要獲得 [1,2,3,4] 的所有排列，您只需要應用spread 4到 [1,2,3] 的所有排列。并且很容易以spread遞回方式撰寫：
spread :: a -> [a] -> [[a]]
spread x [] = [[x]]
spread x (y:ys) = (x:y:ys) : (map (y:) (spread x ys))
因此可以像這樣獲得排列：
permutations :: [a] -> [[a]]
permutations [] = [[]]
permutations (x:xs) = concat (map (spread x) (permutations xs))
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/393119.html