Making A Palindrome
September 29, 2015
Our algorithm works in two passes: First, run through the input accumulating frequency counts of each character. Second, generate the palindrome, or indicate that it is not possible to do so if more than one character occurs an odd number of times; since the problem didn’t specify, we order the characters of the string in increasing order before the center and decreasing order after it:
(define (palin str)
(define (string-reverse str) (list->string (reverse (string->list str))))
(let ((freqs (make-vector 256 0)))
(define (s t i d)
(string-append t
(make-string (/ (vector-ref freqs i) d) (integer->char i))))
(do ((cs (string->list str) (cdr cs))) ((null? cs))
(let ((i (char->integer (car cs))))
(vector-set! freqs i (+ (vector-ref freqs i) 1))))
(let loop ((i 0) (left "") (center ""))
(cond ((= 256 i) (string-append left center (string-reverse left)))
((even? (vector-ref freqs i)) (loop (+ i 1) (s left i 2) center))
((string=? center "") (loop (+ i 1) left (s center i 1)))
(else #f)))))
> (palin "pprrrraaxxxiiiiiissss")
"aiiiprrssxxxssrrpiiia"
This isn’t very good from an efficiency standpoint. The call to string-append is quadratic, and the algorithm as a whole generates a lot of garbage, not to mention the naive impolementation of string-reverse. A better approach modifies the string in-place, once the frequencies are known:
(define (palin str)
(let ((freqs (make-vector 256 0)) (len (string-length str)))
(do ((cs (string->list str) (cdr cs))) ((null? cs))
(let ((i (char->integer (car cs))))
(vector-set! freqs i (+ (vector-ref freqs i) 1))))
(let loop ((i 0) (p 0) (center-char #f) (center-count 0))
(cond ((= 256 i)
(when center-char
(do ((j 0 (+ j 1))) ((= j center-count))
(string-set! str (+ p j) center-char)))
str)
((even? (vector-ref freqs i))
(do ((j 0 (+ j 1)))
((= j (/ (vector-ref freqs i) 2)))
(string-set! str (+ p j) (integer->char i))
(string-set! str (- len p j 1) (integer->char i)))
(loop (+ i 1) (+ p (/ (vector-ref freqs i) 2))
center-char center-count))
((not center-char)
(loop (+ i 1) p (integer->char i) (vector-ref freqs i)))
(else #f)))))
> (palin "pprrrraaxxxiiiiiissss")
"aiiiprrssxxxssrrpiiia"
You can run the program at http://ideone.com/f05O6W.
Programming Praxis 
(Emacs Lisp / Common Lisp)
Simple solution using the loop macro
(defun palindrome-from-string (string) (loop for ch across string with singl = '() and chars = '() do (cond ((member ch singl) (setf singl (remove-if (lambda (c) (eql c ch)) singl)) (push ch chars)) (t (push ch singl))) finally (cond ((<= (length singl) 1) (return (apply #'string (append chars singl (reverse chars))))) (t (return nil)))))Same solution using named let
(defun palindrome-from-string-nlet (string) (nlet loop ((i 0) (l (length string)) (singl '()) (chars '())) (cond ((>= i l) (if (<= (length singl) 1) (apply #'string (append chars singl (reverse chars))) nil)) ((member (aref string i) singl) (loop (+ i 1) l (remove-if (lambda (c) (eql c (aref string i))) singl) (cons (aref string i) chars))) (t (loop (+ i 1) l (cons (aref string i) singl) chars)))))In Python.
from collections import Counter def is_odd(n): return n % 2 == 1 def make_palindrome(s): counter = Counter(s) odd_chars = (c for c, n in counter.items() if is_odd(n)) oddc = next(odd_chars, None) if oddc and (not is_odd(len(s)) or next(odd_chars, None)): return False oddchars = counter.pop(oddc) * [oddc] if oddc else [] evenchars = [c * (n // 2) for c, n in counter.items()] return "".join(evenchars + oddchars + evenchars[::-1])from collections import Counter from collections import deque def make_palindrome(s): # validate ctr = Counter(s) middle_element = None for a in ctr: if ctr[a] % 2: if not middle_element and ctr[a] % 2: middle_element = a else: return None # now make a palindrome result = deque() if middle_element: result.append(middle_element) ctr[middle_element] -= 1 for v in ctr: for i in range(ctr[v]/2): result.append(v) result.appendleft(v) return "".join(result) print make_palindrome('123') print make_palindrome('abcba') print make_palindrome('abba') print make_palindrome('bbbbb') print make_palindrome('89282829282') # output: # None # bacab # baab # bbbbb # 22889298822In brute force. Python’s interaction engine doesn’t print the None that indicates impossibility.
>>> from itertools import permutations >>> next((''.join(p) for p in permutations('pprraxxss') if p == p[::-1]), None) 'prxsasxrp' >>> next((''.join(p) for p in permutations('pprraxxiss') if p == p[::-1]), None) >>>Dumm and Smart in Scala:
package programmingpraxis object MakingPalindrom { def makePalindromSmart(in: String): String = { val freq = in.groupBy(x => (x, in.filter(_ == x).size)).keys val odds = freq.filter(x => x._2 % 2 == 1) val evens = freq.filter(x => x._2 % 2 == 0) if (odds.size > 1) "Not possible" else { val palindromEvensHalf = evens.map(x=>x._1.toString*(x._2/2)).reduce(_+_) val odd = odds.map(x=>x._1.toString*(x._2)).reduce(_+_) palindromEvensHalf+odd+palindromEvensHalf.reverse } } def makePalindromDumm(in: String): String = { if(in.permutations.filter(x=>x==x.reverse).isEmpty) "Not possible" else in.permutations.filter(x=>x==x.reverse).mkString("\r\n") } makePalindromSmart("hello") //> res0: String = Not possible makePalindromSmart("lhelloelh") //> res1: String = ellhohlle makePalindromDumm("hello") //> res2: String = Not possible makePalindromDumm("lhelloelh") //> res3: String = llheoehll //| llehohell //| lhleoelhl //| lhelolehl //| lelhohlel //| lehlolhel //| hlleoellh //| hlelolelh //| hellolleh //| ellhohlle //| elhlolhle //| ehllollhe }Python. The dictionary ‘odd’ is used like a flip-flop to keep track of whether a pair of characters has been seen. If so, add the character to ‘half’; otherwise, put the character in ‘odd’ to indicate it needs a match. At the end, if there is no more than one character that still needs a match, then a palindrome if formed by concatenating ‘half’ with the character than needs a match, if any, and half reversed. If there are more than one character needing a match, then no palindrome is possible.
def makepalindrome(seq): odd = {} half = '' for ch in seq: if odd.pop(ch, False): half += ch else: odd[ch] = True if len(odd) < 2: return half + ''.join(odd.keys()) + half[::-1]A Haskell version.
import Data.List (group, partition, sort) half :: [a] -> [a] half xs = take (length xs `div` 2) xs arrange :: [[a]] -> [[a]] -> [a] arrange ess oss = let es = concatMap half ess in es ++ concat oss ++ reverse es palin :: Ord a => [a] -> Maybe [a] palin xs = case partition (even . length) . group . sort $ xs of (_, _:_:_) -> Nothing (ess, oss) -> Just $ arrange ess oss main :: IO () main = mapM_ (print . palin) ["", "a", "aa", "aaa", "aab", "baab", "babab", "bababa"]I am sure there would be an easier way to do this. But here is mine.
public static String isPalindrome(String str){ String result=""; List<Character> chars = new LinkedList<>(); for(int i=0;i<str.length();i++) chars.add(str.charAt(i)); chars.sort(null); int single=0; char midChar=str.charAt(str.length()-1);//default case if last character for(int i=0;i<chars.size()-1;i++){ if(chars.get(i)!=chars.get(i+1)){ single++; if(single<=1) midChar=chars.get(i); else return "False"; } else{ result=result.substring(0,result.length()/2)+chars.get(i)+chars.get(i)+result.substring(result.length()/2); i++; } } if(str.length()%2==1) result=result.substring(0,result.length()/2)+midChar+result.substring(result.length()/2); if(result.length()==str.length()) return result; else return "False"; }I decided to try to do it in java in as few lines of code as possible. Here’s what I got (13 lines):
import java.util.HashMap;
class Main {
public static void main(String[] args) {
String input = “aaaabbbccdd”;
int numOdd = 0;
HashMap numChars = new HashMap();
for (int k = 0; k 1 ? “Nope!” : “Yup!”);
}
}
looks like 4 of the lines got cut out. Not sure why
@Kevin, paste your Java code between sourcecode tag lines like the following, or look for other workable ways to post source code in the top bar of this site.
[sourcecode lang="java"]
[/sourcecode]
That should be two tag lines in square brackets. Your code between < and > confused a processor that was looking for either some HTML or else these square-bracketed tags (possibly other things that I don’t know about).
I enjoyed mike’s python solution. So I attempted to copy this concept to java
public static String isPalin(String str){ List<String> odd = new ArrayList<>(); // I used a list instead of a dictionary. String half=""; String mid = ""; for(int i =0;i<str.length();i++){ if(odd.contains(str.substring(i,i+1))){ //if odd contains character remove it and add to first half odd.remove(str.substring(i,i+1)); half+=str.charAt(i); }else odd.add(str.substring(i,i+1)); //else add to odd } for(String c:odd) mid+=c; if (mid.length()<2){ return half+mid+new StringBuilder(half).reverse().toString(); } return "Not a Palindrome"; }Here’s another Haskell solution – sort first, then scan the list looking for pairs. Reject if more that one unmatched item found:
import Data.List palin s = makepal (sort s) [] [] where makepal (a:b:s) t u = if a == b then makepal s (a:t) u else checkpal (b:s) t a u makepal [a] t u = checkpal [] t a u makepal [] t u = Just (reverse t ++ u ++ t) checkpal s t a [] = makepal s t [a] checkpal _ _ _ _ = Nothing main = mapM_ (print . palin) ["", "a", "aa", "aaa", "aab", "baab", "babab", "aabbc", "abbcc", "bababa"]“`
from itertools import permutations
def make_palindrome(word):
perms = list(permutations(word))
for i in perms:
if ”.join(i) == ”.join(i)[::-1]:
return ”.join(i)
return False
“`
#include <algorithm> #include <boost/algorithm/string.hpp> #include <boost/optional.hpp> #include <iostream> #include <iterator> #include <string> #include <vector> boost::optional<std::string> make_palindrome(std::string input) { boost::algorithm::to_lower(input); boost::optional<std::string> result; std::string palindrome; boost::optional<char> odd_man_out; //For each character... for (auto i = input.begin(); i != input.end(); ++i) { //Look for a matching character. auto match = std::find(i + 1, input.end(), *i); if (match != input.end()) { //If we find it, remove it from input, & add it to palindrome. input.erase(match); palindrome.push_back(*i); } else { //If we don't find it, if (!odd_man_out) { //If we don't have an odd-man-out, we do now. odd_man_out = *i; } else { //If we already have an odd-man-out, no palindrome. return result; } } } std::string copy(palindrome); if (odd_man_out) palindrome += *odd_man_out; std::copy(copy.rbegin(), copy.rend(), std::back_inserter(palindrome)); return palindrome; } int main(int argc, char** argv) { std::vector<std::string> args(argv + 1, argv + argc); if (args.size() < 1) { args = { "racecar", "aaccerr", "aabbccdd", "boost", }; } for (auto arg: args) { auto palindrome = make_palindrome(arg); std::cout << '"' << arg << "\": "; if (palindrome) std::cout << '"' << *palindrome << "\"\n"; else std::cout << "Cannot become a palindrome.\n"; } }