Create palindrome by rearranging letters of a word Inspired by a recent question that caught my interest (now deleted), I wrote a function in Python 3 to rearrange the letters of a given string to create a (any!) palindrome:


Count the occurrences of each letter in the input
Iterate over the resulting (letter, occurrences) tuples only once: 


If the occurences are even, we remember them to add them around the center later
A valid palindrome can contain only 0 or 1 letter(s) with an odd number of occurrences, so if we've already found the center, we raise an exception. Otherwise, we save the new-found center for later

Finally, we add the sides around the center and join it to create the resulting palindrome string.


I'm looking for feedback on every aspect you can think of, including 


readability (including docstrings),
how appropriate the data structures are,
if the algorithm can be expressed in simpler terms (or replaced altogether) and 
the quality of my tests.




Implementation: palindromes.py

from collections import deque, Counter


def palindrome_from(letters):
    """
    Forms a palindrome by rearranging :letters: if possible,
    throwing a :ValueError: otherwise.
    :param letters: a suitable iterable, usually a string
    :return: a string containing a palindrome
    """
    counter = Counter(letters)
    sides = []
    center = deque()
    for letter, occurrences in counter.items():
        repetitions, odd_count = divmod(occurrences, 2)
        if not odd_count:
            sides.append(letter * repetitions)
            continue
        if center:
            raise ValueError("no palindrome exists for '{}'".format(letters))
        center.append(letter * occurrences)
    center.extendleft(sides)
    center.extend(sides)
    return ''.join(center)




Unit tests: test_palindromes.py (using py.test)

def test_empty_string_is_palindrome():
    assert palindrome_from('') == ''


def test_whitespace_string_is_palindrome():
    whitespace = ' ' * 5
    assert palindrome_from(whitespace) == whitespace


def test_rearranges_letters_to_palindrome():
    assert palindrome_from('aabbb') == 'abbba'


def test_raises_exception_for_incompatible_input():
    with pytest.raises(ValueError) as error:
        palindrome_from('asdf')
    assert "no palindrome exists for 'asdf'" in error.value.args




Manual testing in the console

while True:
    try:
        word = input('Enter a word: ')
        print(palindrome_from(word))
    except ValueError as e:
        print(*e.args)
    except EOFError:
        break
from collections import deque, Counter


def palindrome_from(letters):
    """
    Forms a palindrome by rearranging :letters: if possible,
    throwing a :ValueError: otherwise.
    :param letters: a suitable iterable, usually a string
    :return: a string containing a palindrome
    """
    counter = Counter(letters)
    sides = []
    center = deque()
    for letter, occurrences in counter.items():
        repetitions, odd_count = divmod(occurrences, 2)


odd_count is a bit of a strange name, because its just whether its odd or even, not really an odd_count

        if not odd_count:
            sides.append(letter * repetitions)
            continue


avoid using continue, favor putting the rest of the loop in an else block. Its easier to follow that way

        if center:
            raise ValueError("no palindrome exists for '{}'".format(letters))
        center.append(letter * occurrences)
    center.extendleft(sides)
    center.extend(sides)


Avoid reusing variables for something different. Changing center to be the whole phrase isn't all that good an idea. I suggest using itertools.chain(sides, center, reversed(sides)) and then joining that.

    return ''.join(center)