Create palindrome by rearranging letters of a word

Question

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:

1. Count the occurrences of each letter in the input
2. 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
3. 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

• spyr03: Rather than checking if you already have a letter with odd frequency, you can just count how many you have total, and if it is not equal to mod2 of the length of the string, it can't be a palindrome. In other words, if(number_of_odd_frequencies == len(word) % 2): it is a palindrome

Answer 1

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)

• Adam: Interesting! Using itertools.chain eliminates the need to use a deque I guess. You need to do reversed(sides) for the last argument though (the deque used to do that by itself for some reason).
• Winston Ewert: @codesparkle, ah I suppose extendleft probably extends in the backwards order.