anagram finder / dict mapping question

[dave]

Hi All,

I wrote a program that takes a string sequence and finds all the words
inside a text file (one word per line) and prints them:

def anagfind(letter s): #find anagrams of these letters
fin = open('text.txt' ) #one word per line file
wordbox = [] #this is where the words will go
for line in fin:
word = line.strip()
count = 0
for char in letters:
if char not in word:
break
else:
count += 1
if count == len(word):
wordbox.append( word)
return wordbox

Now I'd like to modify the code to naturally find all anagrams inside a
wordlist. What would be the best way to do this? Using Hints? Is it
possible to iterate over dict keys? How can I make a dict that maps
from a set of letters to a list of words that are spelled from those
letters? Wouldn't I need to make the set of letters a key in a dict?

As always - Thanks for helping someone trying to learn...

Dave

[Kam-Hung Soh]

On Thu, 08 May 2008 11:02:12 +1000, dave <sq************ *@1ya2hoo3.net
wrote:

Hi All,

I wrote a program that takes a string sequence and finds all the words
inside a text file (one word per line) and prints them:

def anagfind(letter s): #find anagrams of these letters
fin = open('text.txt' ) #one word per line file
wordbox = [] #this is where the words will go
for line in fin:
word = line.strip()
count = 0
for char in letters:
if char not in word:
break
else:
count += 1
if count == len(word):
wordbox.append( word)
return wordbox

Now I'd like to modify the code to naturally find all anagrams inside a
wordlist. What would be the best way to do this? Using Hints? Is it
possible to iterate over dict keys? How can I make a dict that maps
from a set of letters to a list of words that are spelled from those
letters? Wouldn't I need to make the set of letters a key in a dict?

As always - Thanks for helping someone trying to learn...

Dave

Suggestion: for each word, sort their characters and use them as the
dictionary key. If two words have the same combination of characters,
then they are anagrams. For example: "edam" and "made" are anagrams
because they have the letters 'a', 'd', 'e' and 'm'.

Refer "Programmin g Pearls" by Jon Bentley.

--
Kam-Hung Soh <a href="http://kamhungsoh.com/blog">Software Salariman</a>

[dave]

This is what i've came up with. My problem is that I can't get them to
properly evaluate.. when comparewords() runs it finds itself...
Should I have the keys of mapdict iterate over itself? Is that
possible?

def annafind():
fin = open('text.txt' ) # file has one word per line
mapdic = {} # each word gets sorted & goes in here
for line in fin:
rawword = line.strip()
word = list(rawword)
word.sort()
mapdic[''.join(word)] = 0
return mapdic
def comparewords(): ***not working as intended
fin = open('text.txt' )
for line in fin:
line = line.strip()
word = list(line)
word.sort()
sortedword = (''.join(word))
if sortedword in mapdic:
print line


On 2008-05-07 19:25:53 -0600, "Kam-Hung Soh" <ka*********@gm ail.comsaid:

On Thu, 08 May 2008 11:02:12 +1000, dave <sq************ *@1ya2hoo3.net>
wrote:

>Hi All,

I wrote a program that takes a string sequence and finds all the words

>inside a text file (one word per line) and prints them:

def anagfind(letter s): #find anagrams of these letters
fin = open('text.txt' ) #one word per line file
wordbox = [] #this is where the words will go
for line in fin:
word = line.strip()
count = 0
for char in letters:
if char not in word:
break
else:
count += 1
if count == len(word):
wordbox.append( word)
return wordbox

Now I'd like to modify the code to naturally find all anagrams inside

a

>wordlist. What would be the best way to do this? Using Hints? Is it

>possible to iterate over dict keys? How can I make a dict that maps

>from a set of letters to a list of words that are spelled from those

>letters? Wouldn't I need to make the set of letters a key in a dict?

As always - Thanks for helping someone trying to learn...

Dave

Suggestion: for each word, sort their characters and use them as the
dictionary key. If two words have the same combination of characters,
then they are anagrams. For example: "edam" and "made" are anagrams
because they have the letters 'a', 'd', 'e' and 'm'.

Refer "Programmin g Pearls" by Jon Bentley.

--
Kam-Hung Soh <a href="http://kamhungsoh.com/blog">Software Salariman</ a>

[Kam-Hung Soh]

On Thu, 08 May 2008 15:42:07 +1000, dave <sq************ *@1ya2hoo3.net
wrote:

This is what i've came up with. My problem is that I can't get them to
properly evaluate.. when comparewords() runs it finds itself... Should
I have the keys of mapdict iterate over itself? Is that possible?

def annafind():
fin = open('text.txt' ) # file has one word per line
mapdic = {} # each word gets sorted & goes in here
for line in fin:
rawword = line.strip()
word = list(rawword)
word.sort()
mapdic[''.join(word)] = 0
return mapdic
def comparewords(): ***not working as intended
fin = open('text.txt' )
for line in fin:
line = line.strip()
word = list(line)
word.sort()
sortedword = (''.join(word))
if sortedword in mapdic:
print line


On 2008-05-07 19:25:53 -0600, "Kam-Hung Soh" <ka*********@gm ail.com
said:

>On Thu, 08 May 2008 11:02:12 +1000, dave <sq************ *@1ya2hoo3.net>
wrote:

>>Hi All,
I wrote a program that takes a string sequence and finds all the words

>>inside a text file (one word per line) and prints them:
def anagfind(letter s): #find anagrams of these letters
fin = open('text.txt' ) #one word per line file
wordbox = [] #this is where the words will go
for line in fin:
word = line.strip()
count = 0
for char in letters:
if char not in word:
break
else:
count += 1
if count == len(word):
wordbox.append( word)
return wordbox
Now I'd like to modify the code to naturally find all anagrams inside

a

>>wordlist. What would be the best way to do this? Using Hints? Is it

>>possible to iterate over dict keys? How can I make a dict that maps

>>from a set of letters to a list of words that are spelled from those

>>letters? Wouldn't I need to make the set of letters a key in a dict?
As always - Thanks for helping someone trying to learn...
Dave

Suggestion: for each word, sort their characters and use them as the
dictionary key. If two words have the same combination of characters,
then they are anagrams. For example: "edam" and "made" are anagrams
because they have the letters 'a', 'd', 'e' and 'm'.
Refer "Programmin g Pearls" by Jon Bentley.
--
Kam-Hung Soh <a href="http://kamhungsoh.com/blog">Software Salariman</
a>

Your code is always going to return the same list because every word is an
anagram of itself.

Tip: Create a list for each dictionary key, then add a word to the list if
that word is not in the list. So:

mapdic('adem') --["edam", "made"]

P.S. When replying, the convention is to add your response to the bottom,
not top of the message.

--
Kam-Hung Soh <a href="http://kamhungsoh.com/blog">Software Salariman</a>

[offby1]

Been there, done that:
http://polyglot-anagrams.googlecode..../trunk/python/

[dave]

>On 2008-05-07 19:25:53 -0600, "Kam-Hung Soh" <ka*********@gm ail.com>

>

>said:

>>On Thu, 08 May 2008 11:02:12 +1000, dave <sq************ *@1ya2hoo3.ne

t>

>>wrote:

Hi All,
I wrote a program that takes a string sequence and finds all the wo

rds

>>>
inside a text file (one word per line) and prints them:
def anagfind(letter s): #find anagrams of these letters
fin = open('text.txt' ) #one word per line file
wordbox = [] #this is where the words will go
for line in fin:
word = line.strip()
count = 0
for char in letters:
if char not in word:
break
else:
count += 1
if count == len(word):
wordbox.append( word)
return wordbox
Now I'd like to modify the code to naturally find all anagrams insi

de

>>a
wordlist. What would be the best way to do this? Using Hints? Is

it

>>>
possible to iterate over dict keys? How can I make a dict that maps

>>>
from a set of letters to a list of words that are spelled from those

>>>
letters? Wouldn't I need to make the set of letters a key in a dict

?

>>> As always - Thanks for helping someone trying to learn...
Dave

Suggestion: for each word, sort their characters and use them as the

>>dictionary key. If two words have the same combination of characters

,

>>then they are anagrams. For example: "edam" and "made" are anagrams
because they have the letters 'a', 'd', 'e' and 'm'.
Refer "Programmin g Pearls" by Jon Bentley.
--
Kam-Hung Soh <a href="http://kamhungsoh.com/blog">Software Salarima

n</

>>a>

Your code is always going to return the same list because every word is an
anagram of itself.

Tip: Create a list for each dictionary key, then add a word to the list if
that word is not in the list. So:

mapdic('adem') --["edam", "made"]

P.S. When replying, the convention is to add your response to the bottom ,
not top of the message.

--
Kam-Hung Soh <a href="http://kamhungsoh.com/blog">Software Salariman</ a>

I got it! Thanks for all your help!!! Please tell me what you think:

def anafind():
fin = open('short.txt ') #one word per line
mapdic = {} #this dic maps letters to anagrams
for line in fin:
line = line.strip()
templist = sorted(list(lin e)) #sort letters
newtlist = (''.join(templi st)) #join letters
if newtlist not in mapdic:
mapdic[newtlist] = [line]
if line not in mapdic[newtlist]:
mapdic[newtlist].append(line)
for value in mapdic.values() :
if len(value) <= 1:
pass
else:
print value

[Paul Rubin]

dave <sq************ *@1ya2hoo3.netw rites:

if newtlist not in mapdic:
mapdic[newtlist] = [line]
if line not in mapdic[newtlist]:
mapdic[newtlist].append(line)

I'd use the defaultdict module to avoid the above.

for value in mapdic.values() :
if len(value) <= 1:
pass
else:
print value

I'd write:

for value in mapdic.values() :
if len(value) 1:
print value

I'd actually use itervalues rather than values, but that's a little
bit fancy, you don't have to worry about it til later.

[Kam-Hung Soh]

On Fri, 09 May 2008 09:52:53 +1000, dave <sq************ *@1ya2hoo3.net
wrote:

I got it! Thanks for all your help!!! Please tell me what you think:

def anafind():
fin = open('short.txt ') #one word per line
mapdic = {} #this dic maps letters to anagrams
for line in fin:
line = line.strip()
templist = sorted(list(lin e)) #sort letters
newtlist = (''.join(templi st)) #join letters
if newtlist not in mapdic:
mapdic[newtlist] = [line]
if line not in mapdic[newtlist]:
mapdic[newtlist].append(line)
for value in mapdic.values() :
if len(value) <= 1:
pass
else:
print value

I avoid creating a temporary variable if it's only used once immediately,
so I would have written:

newtlist = ''.join(sorted( list(line)))

Looks pretty good, and I found the other tips in parallel responses useful
to me too!

--
Kam-Hung Soh <a href="http://kamhungsoh.com/blog">Software Salariman</a>

[Jerry Hill]

On Thu, May 8, 2008 at 7:52 PM, dave <sq************ *@1ya2hoo3.netw rote:

I got it! Thanks for all your help!!! Please tell me what you think:

Here's yet another version of the same thing, using defaultdicts and
sets. This way we don't have to test for membership in either the
dictionary or the collection of anagrams. The code is shorter, but no
less readable in my opinion.

from collections import defaultdict

def anafind(words):
"""
Given a sequence of words, return a dictionary with groups
of letters as keys and sets of anagrams as values
"""
anagrams = defaultdict(set )
for word in words:
key = ''.join(sorted( word))
anagrams[key].add(word)
return anagrams

if __name__ == "__main__":
wordlist = ['live', 'evil', 'one', 'nose', 'vile', 'neo']
anagrams = anafind(wordlis t)
for letters, words in anagrams.items( ):
print "%s: %s" % (letters, words)

--
Jerry

[Arnaud Delobelle]

"Kam-Hung Soh" <ka*********@gm ail.comwrites:

I avoid creating a temporary variable if it's only used once
immediately, so I would have written:

newtlist = ''.join(sorted( list(line)))

Or ''.join(sorted( line))

as sorted() works with any iterable.

--
Arnaud