Haskell Wie generiere ich alle möglichen Palindrome

Question

Wie erzeugt man alle möglichen Palindrome der Länge n?

die einzigen Zeichen ['a'..'z'] sollte

palindrome n :: Integer -> [String] 

Answer 1

Selbst Fall

Lets für nehmen erste Einfachheit verwendet werden, dass n auch ist, später können wir die Funktion verallgemeinern. Wir können Rekursion dafür verwenden. Wir definieren eine Hilfsfunktion pal' :: Integer -> [String] -> [String]. Hier ist das zweite Argument die akkumulierte umgekehrte Zeichenkette. Also, wenn wir 0 schlagen wir einfach eine einzige Liste emittieren müssen, um die die akkumulierte umgekehrt String enthalten, wie:

pal' 0 r = [r] 

Da jedoch sind wir noch in der Erzeugung Teil des Palindrom, also die linke Seite, können wir Liste Verständnis verwenden, wie:

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

so iterieren wir über [a..z] und für jeden solchen Charakter, wir uns einen rekursiven Aufruf auf pal' durchführen, wo wir ein zusätzlichen k-1 Zeichen generieren müssen, mit (c:r) als umgekehrte Zeichenfolge, die ausgegeben werden soll. Außerdem liefern wir für diese Palindrome c : p. Wir stellen damit den choses Charakter vor das Palindrom.

So, jetzt für eine even_palindrome Funktion, die sogar Palindrome erzeugt, können wir schreiben:

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

Zu Testzwecken habe ich den Code aus dem Bereich holen `c < - [ 'a'. .'d '], aber Sie können es auf einen beliebigen Bereich einstellen.

Und wenn wir Palindrome für Länge 0, 2 und 4 erzeugen, erhalten wir:

*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"] 

Damit scheint zu funktionieren. Wenn wir jedoch evenpalindrome 1 schreiben, wird es in dem Sinne arbeitet, dass es Integer-Division nehmen, und somit Palindrome für Länge erzeugen 0.

Odd Fall

Nun ist die Frage, was müssen wir ändern, um zu lass es für ungerade Länge arbeiten. Es gibt zwei Dinge, die ändern müssen:

1. wir ein zusätzliches Zeichen generieren müssen, also sollten wir div n 2 nicht verwenden, aber div (n+1) 2; und
2. das letzte generierte Zeichen sollte nicht im umgekehrten Fall wiederholt werden.

So bedeutet es, dass wir zuerst n Modulo 2 überprüfen sollten, (lassen, dass d sein) und dann neu zu schreiben:

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

Darüber wie gesagt, bevor wir die anfänglichen pal' mit pal' (div (n+1) 2) [] nennen sollen, so jetzt die verallgemeinerte Version ist:

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 

Welche produziert:

*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"] 

Speicherstruktur

Eine nette Sache über den umgekehrten Teil Rekursion auf diese Weise mit der Konstruktion ist, dass die zweite Hälfte aller Palindrome ist effizienter gespeichert. Gegeben wir Palindrome der Länge 5 für den `[ 'a' .. 'b'] Bereich, die endgültige Liste (nach vollständiger Auswertung) erzeugen, wird wie folgt aussehen:

+---+ 
| 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

Ein Palindrom ist ein String, wo die letzten Die Hälfte der Zeichen ist die Umkehrung der ersten Hälfte der Zeichen. Daher wäre ein einfacher Algorithmus, alle Zeichenfolgen der Länge n/2 zu generieren und dann die Umkehrung jeder Zeichenfolge an das Ende anzuhängen. Für Palindrome mit ungerader Länge können wir einfach das erste Zeichen der hinteren Hälfte der Zeichenfolge löschen und sicherstellen, dass wir aufgerundet werden, wenn wir n/2 finden.

Jetzt ist der schwierige Teil erzeugt alle möglichen Strings der Länge n/2. Wir müssen ein Zeichen aus ['a'..'z'] für jedes Zeichen in der Zeichenfolge und in Haskell, lists can represent non-determinism auswählen. Daher müssen wir nur replicateM verwenden und es wird jede Zeichenkette erzeugt, bei der jedes Zeichen nicht-deterministisch aus dem Alphabet gewählt wird.

Eine Randnotiz, die Zahl der möglichen Palindrome für jede Länge n steigt mit einer exponentiellen Rate. Die Verwendung eines Integer als Eingabe ist Overkill, da der Maximalwert eines Int bereits über 9 Trillionen beträgt.

Hier ist ein Weg, um den vollen Algorithmus zu implementieren:

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