Я так понимаю, это домашнее задание. Вы знаете, что анаграммы — это просто перестановки слов. Не торопитесь: научитесь вычислять анаграмму для одного слова, прежде чем вы научитесь делать это для многих слов. Следующий интерактивный сеанс показывает, как вычислить анаграмму слова. Вы можете продолжить оттуда.
>>> # Learn how to calculate anagrams of a word
>>>
>>> import itertools
>>>
>>> word = 'fun'
>>>
>>> # First attempt: anagrams are just permutations of all the characters in a word
>>> for permutation in itertools.permutations(word):
... print permutation
...
('f', 'u', 'n')
('f', 'n', 'u')
('u', 'f', 'n')
('u', 'n', 'f')
('n', 'f', 'u')
('n', 'u', 'f')
>>>
>>> # Now, refine the above block to print actual words, instead of tuple
>>> for permutation in itertools.permutations(word):
... print ''.join(permutation)
...
fun
fnu
ufn
unf
nfu
nuf
>>> # Note that some words with repeated characters such as 'all'
>>> # has less anagrams count:
>>> word = 'all'
>>> for permutation in itertools.permutations(word):
... print ''.join(permutation)
...
all
all
lal
lla
lal
lla
>>> # Note the word 'all' and 'lla' each repeated twice. We need to
>>> # eliminate redundancy. One way is to use set:
>>> word = 'all'
>>> anagrams = set()
>>> for permutation in itertools.permutations(word):
... anagrams.add(''.join(permutation))
...
>>> anagrams
set(['lal', 'all', 'lla'])
>>> for anagram in anagrams:
... print anagram
...
lal
all
lla
>>> # How many anagrams does the word 'all' have?
>>> # Just count using the len() function:
>>> len(anagrams)
3
>>>
Я вставил приведенный выше сеанс здесь для вашего удобства.
Обновлять
Теперь с разъяснением Аарона. Проблема на самом низком уровне: как определить, являются ли два слова анаграммами? Ответ: "Когда в них одинаковое количество букв". Самый простой способ ( для меня) состоит в том, чтобы отсортировать все буквы и сравнить их.
def normalize(word):
word = word.strip().lower() # sanitize it
word = ''.join(sorted(word))
return word
# sort_letter('top') ==> 'opt'
# Are 'top' and 'pot' anagrams? They are if their sorted letters are the same:
if normalize('top') == normalize('pot'):
print 'they are the same'
# Do something
Теперь, когда вы знаете, как сравнивать два слова, давайте поработаем со списком слов:
>>> import collections
>>> anagrams = collections.defaultdict(list)
>>> words = ['top', 'fun', 'dog', 'opt', 'god', 'pot']
>>> for word in words:
... anagrams[normalize(word)].append(word)
...
>>> anagrams
defaultdict(<type 'list'>, {'opt': ['top', 'opt', 'pot'], 'fnu': ['fun'], 'dgo': ['dog', 'god']})
>>> for k, v in anagrams.iteritems():
... print k, '-', v
...
opt - ['top', 'opt', 'pot']
fnu - ['fun']
dgo - ['dog', 'god']
В приведенном выше сеансе мы используем анаграммы (слово по умолчанию, то же самое, что и словарь со значениями по умолчанию) для хранения списка слов. Ключи - это отсортированные буквы. Это означает, anagrams['opt'] ==> ['top', 'opt', 'pot']
. Оттуда вы можете сказать, у кого больше всего анаграмм. Остальное должно быть достаточно легко.
person
Hai Vu
schedule
15.03.2013