[Tutor] Anagram creator

[spir]

Le samedi 27 décembre 2008 à 19:32 -0500, btkuhn at email.unc.edu a
écrit : 
> Hi everyone,
> 
> I'm having trouble with an anagram generating program that I am writing 
> in Python. My output is not what it should be and I think the reason 
> has something to do with my helper functions creating a reference to a 
> dictionary each time it is called rather than a new "clone" dictionary. 
> Here is my main function, with explanation afterward:
> 
> 
>     def anagramsHelper(phrase,dictionary,anagramsofar):        if 
> isSolved(phrase): #returns true if the dictonary for the phrase is empty
>             print anagramsofar
>                       return True
>         for word in dictionary:
>             if wordCanBeMade(word, phrase):
>                 anagramsofar=anagramsofar+" "+word
>                 phraseclone=removeLetters(word, phrase)
>                 anagramsHelper(phraseclone,dictionary,anagramsofar)
> 

There is a layout issue with this func. I guess the proper code is probably as below
(I renamed the func for the code to fit in usual width) :

def anagrHelp(phrase,dictionary,anagramsofar):
	if isSolved(phrase): #returns true if the dict is empty
		print anagramsofar
		return True
	for word in dictionary:
		if wordCanBeMade(word, phrase):
			anagramsofar=anagramsofar+" "+word
			phraseclone=removeLetters(word, phrase)
			anagrHelp(phraseclone,dictionary,anagramsofar)



> Initially it takes a dictionary representing a word or phrase (eg 
> {'a':2,'d':1, 'e':2}), a dictionary in the form of a list of words, and 
> anagramsofar which is initially passed as "".
> Next, isSolved returns true if the dictionary is empty, meaning that 
> all letters in the phrase have been used up. Otherwise, for each word 
> in the dictionary, the program tests whether the word can be made from 
> letters in the phrase. If it can, the word is appended to phrasesofar. 
> removeLetters then removes the letters that were used to make the word. 
> I saved the new phrase as phraseclone as an attempt to troubleshoot; 
> originally I just used the original phrase variable. Next, the function 
> is recursively called with the letters removed from the phrase. The end 
> result is that when the phrase dictionary is empty, "anagramsofar" is 
> printed. This should generate all anagrams of a given phrase using a 
> given dictionary of words.

I think the issue lays in the combination of loop and recursive call
(which is often a very subtile feature).

You current status is both held by angramsofar (constructed new phrase)
and phrase (unused char list). So that if you want to find it back when
backtracking to a previous stage, you need to find them both at their
value for this stage. Which means that both must be copied to be passed
as arguments for a recursive call. As of now, only phrase is cloned. So
that anagramsofar can only grow...

Denis