W10D1.py

# Python implementations of the same functionality as in
# https://gist.github.com/Rosuav/9c43bd978e2a794470436e9c3e3769c4
# Note that these functions can be used with strings containing any
# Unicode characters, and will be reliable. (Assumes Python 3.3 or newer.)

# Python provides a handy variant of mapping that will automatically
# create entries as we need them. It's called collections.defaultdict,
# and would save us a bit of work. But in the interests of algorithmic
# clarity, I have avoided its use here.

# Write an algorithm to check whether any permutation of a string is a
# palindrome (a string which reads the same forwards and backwards).
# Note that this does not use the HashMap class due to a lack of useful
# features such as iteration. The core algorithm would work the same way
# though.
def any_palindromes(word):
	letter_count = {}
	for letter in word:
		if letter in letter_count: letter_count[letter] += 1
		else: letter_count[letter] = 1
	have_odd = False
	for count in letter_count.values():
		if count & 1:
			# There are an odd number of this letter. A
			# palindrome is possible with one such letter, but
			# no more, so flag and carry on.
			if have_odd: return False
			have_odd = True
	return True

# Write an algorithm to group a list of words into anagrams.

def _sortword(word):
	# Helper function: sort a word into some form of canonical order.
	# The exact order is insignificant and need not be lexicographical,
	# as long as it is utterly consistent: any two anagrams of the same
	# letter sequence must return the same string.
	return ''.join(sorted(word))

def group_into_anagrams(words):
	anagrams = {}
	for word in words:
		key = _sortword(word)
		if key not in anagrams: anagrams[key] = []
		anagrams[key].append(word)
	return list(anagrams.values())