Skip to content

Instantly share code, notes, and snippets.

@leegao
Created February 13, 2012 20:30
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save leegao/1819957 to your computer and use it in GitHub Desktop.
Save leegao/1819957 to your computer and use it in GitHub Desktop.
How many anagrams are there?
# Assume the average length m of each word << the length of the list of words, which we call n
# The following will run in O(n*mlgm) Now assuming that we're using words from
# the english language, then the mlgm factor goes to around 6*C
# so the overall runtime should scale linearly with the size of the input length
def anagrams(file):
dict = {}
count = set()
for line in open(file):
sline = "".join(sorted(line))
if sline in dict:
count.add(sline) # change to line to find how many are part of the list of anagrams
dict[sline] = 0
return len(count)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment