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.

Advertisements

Pages: 1 2

15 Responses to “Making A Palindrome”

  1. wert310 said

    (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)))))
    
  2. Paul said

    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])
    
  3. Rutger said
    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
    # 22889298822
    
  4. Jussi Piitulainen said

    In 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)
    >>> 
    
  5. FA said

    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
     
    }
    
  6. Mike said

    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]
    
  7. Globules said

    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"]
    
    $ ./palin 
    Just ""
    Just "a"
    Just "aa"
    Just "aaa"
    Just "aba"
    Just "abba"
    Just "abbba"
    Nothing
    
  8. 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";
    			
    }	
    
  9. Kevin said

    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!”);
    }
    }

  10. Kevin said

    looks like 4 of the lines got cut out. Not sure why

  11. Jussi Piitulainen said

    @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).

  12. 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";
    	}
    
  13. matthew said

    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"]
    
  14. alifaki said

    “`
    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
    “`

  15. fisherro said
    #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";
        }
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: