Haskell 如何生成所有可能的回文

Question

如何生成长度为n的所有可能回文？

应该使用唯一的字符 ['a'..'z']

palindrome n :: Integer -> [String]

Answer 1

偶数

为了简单起见[=66=]首先假设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 屈服。这样我们就把choses字符放在了回文前面。

所以现在对于生成 even 回文的 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 <- ['a'..'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 的回文。

奇数

现在的问题是我们必须改变什么才能让它在奇数长度下工作。这里有两件事需要改变：

我们需要生成一个额外的字符，所以我们不应该使用div n 2，而是div (n+1) 2；和
在相反的情况下，最后生成的字符应该不重复。

所以这意味着我们应该首先检查 n 模 2（令其为 d），然后重写：

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

另外前面说了要用pal' (div (n+1) 2) []来调用初始的pal'，所以现在通用的版本是：

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'..'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. Therefore, all we need to do is use replicateM 中，它将创建每个字符串，其中每个字符都是从字母表中非确定性地选择的。

旁注，任何长度 n 可能的回文数以指数速率增加。使用 Integer 作为输入有点矫枉过正，因为 Int 的最大值已经超过 9 quintillion。

这是实现完整算法的一种方法：

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']

Haskell 如何生成所有可能的回文

Haskell How to generate all possible Palindromes

haskell

palindrome

偶数

奇数

内存结构