Haskell如何生成所有可能的迴文錄碼

Question

如何生成長度爲n的所有可能的迴文數？

唯一字符['a'..'z']應使用

palindrome n :: Integer -> [String] 

Answer 1

即使情況

讓我們爲簡單起見首先假設n甚至，以後我們可以概括的功能。我們可以爲此使用遞歸。我們定義了一個幫助函數pal' :: Integer -> [String] -> [String]。這裏的第二個參數是累加的反向字符串。所以一旦我們打0，我們只需要發出一個單一的列表中包含的累積逆轉字符串，如：

pal' 0 r = [r] 

鑑於但是我們仍然在迴文結構產生部分，左側因此，我們可以使用列表理解，如：

pal' k r = [ c : p | c <- ['a'..'z'], p <- pal' (k-1) (c:r) ] 

所以我們遍歷[a..z]併爲每個這樣的字符，我們對我們進行pal'遞歸調用，我們需要生成一個附加k-1字符，(c:r)作爲反向字符串發射。此外，我們爲這些迴文產生c : p。我們把這個選擇字符放在迴文前面。

所以現在的even_palindrome功能產生甚至迴文，我們可以這樣寫：

evenpalindrome :: Integer -> [String] 
evenpalindrome n = pal' (div n 2) [] 
    where pal' 0 r = [r] 
      pal' k r = [ c : p | c <- ['a'..'z'], p <- pal' (k-1) (c:r) ] 

出於測試目的，我設置的代碼'C <的範圍內挑選 - [「一」。 。'd']，但您可以將其設置爲您想要的任何範圍。

如果我們生成長度0,2和4迴文，我們得到：

*Main> evenpalindrome 0 
[""] 
*Main> evenpalindrome 2 
["aa","bb","cc","dd"] 
*Main> evenpalindrome 4 
["aaaa","abba","acca","adda","baab","bbbb","bccb","bddb","caac","cbbc","cccc","cddc","daad","dbbd","dccd","dddd"] 

所以這似乎工作。如果我們寫不過evenpalindrome 1，它會在這個意義上的工作，將採取整數除法，並因此產生了長度爲0

奇數的情況下回文

現在的問題是我們有什麼以改變到讓它適用於奇數長度。有需要改變這裏兩件事情：

1. 我們需要生成一個附加的性格，所以我們不應該使用div n 2，但div (n+1) 2;和
2. 最後生成的字符應該是而不是可以在相反的情況下重複。

因此，這意味着，我們應該先檢查n模2（那一定是d），然後改寫：

pal' 0 r = [drop (fromInteger d) r] 

而且爲說，我們應該叫初始pal'與pal' (div (n+1) 2) []之前，所以現在廣義的版本是：

palindrome :: Integer -> [String] 
palindrome n = pal' (div (n+1) 2) [] 
    where pal' 0 r = [drop (fromInteger d) r] 
      pal' k r = [ c : p | c <- ['a'..'z'], p <- pal' (k-1) (c:r) ] 
      d = mod n 2 

主要生產：

*Main> palindrome 1 
["a","b","c","d"] 
*Main> palindrome 2 
["aa","bb","cc","dd"] 
*Main> palindrome 3 
["aaa","aba","aca","ada","bab","bbb","bcb","bdb","cac","cbc","ccc","cdc","dad","dbd","dcd","ddd"] 
*Main> palindrome 4 
["aaaa","abba","acca","adda","baab","bbbb","bccb","bddb","caac","cbbc","cccc","cddc","daad","dbbd","dccd","dddd"] 
*Main> palindrome 5 
["aaaaa","aabaa","aacaa","aadaa","ababa","abbba","abcba","abdba","acaca","acbca","accca","acdca","adada","adbda","adcda","addda","baaab","babab","bacab","badab","bbabb","bbbbb","bbcbb","bbdbb","bcacb","bcbcb","bcccb","bcdcb","bdadb","bdbdb","bdcdb","bdddb","caaac","cabac","cacac","cadac","cbabc","cbbbc","cbcbc","cbdbc","ccacc","ccbcc","ccccc","ccdcc","cdadc","cdbdc","cdcdc","cdddc","daaad","dabad","dacad","dadad","dbabd","dbbbd","dbcbd","dbdbd","dcacd","dcbcd","dcccd","dcdcd","ddadd","ddbdd","ddcdd","ddddd"] 

存儲器結構

約構建使用遞歸這種方式反向部分A好處，就是所有的迴文的第二半被更有效地存儲。鑑於我們產生了`[「A」 ..「B」]範圍內，最終名單長度爲5迴文（完整的評估後），會看起來像：

+---+ 
| o--- 'a' -- 'a' -> 'a' -\ 
+---+      > 'a' -\ 
| o--> 'a' -> 'a' -> 'b' -/  \ 
+---+        > 'a' 
| o--> 'a' -> 'b' -> 'a' -\  /
+---+      > 'b' -/ 
| o--> 'a' -> 'b' -> 'b' -/ 
+---+ 
| o--> 'b' -> 'a' -> 'a' -\ 
+---+      > 'a' -\ 
| o--> 'b' -> 'a' -> 'b' -/  \ 
+---+        > 'b' 
| o--> 'b' -> 'b' -> 'a' -\  /
+---+      > 'b' -/ 
| o--> 'b' -> 'b' -> 'b' -/ 
+---+

Answer 2

迴文是一個字符串，其中最後一個一半的字符與前半部分字符相反。因此，一個簡單的算法將生成長度爲n/2的所有字符串，然後將每個字符串的反轉附加到末尾。對於奇數長度的迴文，我們可以放棄字符串後半部分的第一個字符，並且當我們找到n/2時確保四捨五入。

現在棘手的部分是產生長度爲n/2的所有可能的字符串。我們需要爲字符串中的每個字符從['a'..'z']中選擇一個字符，並在Haskell中選擇lists can represent non-determinism。因此，我們所需要做的就是使用replicateM，它會創建每個字符串，其中每個字符都是從字母表中非確定性地選擇的。

附註中，任何長度n可能的迴文數可能以指數速率增加。使用Integer作爲輸入是矯枉過正的，因爲Int的最大值已經超過9個百分點。

下面就來實現完整的算法的一種方法：

palindrome :: Int -> [String] 
palindrome n 
    | n < 0 = [] 
    | even n = map (\front -> front ++ reverse front) fronts 
    | odd n = map (\front -> front ++ tail (reverse front)) fronts 
    where fronts = replicateM (div (n + 1) 2) ['a'..'z']