Making A Palindrome
September 29, 2015
We have today a small exercise in string manipulation: Given an input string, either return a string containing the same characters but arranged to form a palindrome, or indicate that no such rearrangement is possible.
Your task is to write the program that creates a palindrome. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
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"; } }