Programming Forums - What's wrong with this code?

Programming Forums (http://www.programmingforums.org/forumindex.php)

- Python (http://www.programmingforums.org/forum43.html)

- - What's wrong with this code? (http://www.programmingforums.org/showthread.php?t=10254)

What's wrong with this code?

I'm writing a function that takes a number (eg, 2345) and selects those names from a pre-defined list of names (in a text file) that can be formed by replacing each number with one of three corresponding letters, shown below:

2: ['A', 'B', 'C']

3: ['D', 'E', 'F']

4: ['G', 'H', 'I']

5: ['J', 'K', 'L']

6: ['M', 'N', 'O']

7: ['P', 'R', 'S']

8: ['T', 'U', 'V']

9: ['W', 'X', 'Y']

I wrote a recursive function to create a list of all possible combinations of letters, then select those that match up to names in the pre-defined list of names. This worked but was extremely slow for longer numbers (up to 12 digits). I figure (although I may be wrong) that such an algorithm would be O(3^n) -- Is that correct?

# works, but slow

def lettercombos(num):

        if (len(num) == 1):

                return numdict[int(num)]

        for n in num:

                ret = []

                for l in numdict[int(n)]:

                        for x in lettercombos(num[1:]):

                                ret.append(l + x)

                return ret

My next approach was to first remove all names from the list that were not the same length as the number. Then, I iterate through each digit of the number, and remove names from the new list of names that do not have the corresponding letters for that number in that location. I ended up writing the following code:

# does not work

for i in range(len(num)):

        letters = numdict[int(num[i])]

        for name in namelist:

                if name[i] not in letters:

                        namelist.remove(name)

However, this does not work properly. I cannot figure out what is going wrong. Am I using the list.remove() function correctly? I can't seem to figure out what the problem could be.

Thanks for your help.

I think the problem may be that it's iterating through a list that you're changing.

Create a temporary copy of the list before, then copy back after like so:

# does not work

for i in range(len(num)): # i is the index of each digit

        letters = numdict[int(num[i])]

        templist = namelist[:] # create a direct copy of the list rather then referencing it

        for name in namelist:

                if name[i] not in letters:

                        templist.remove(name)

        namelist = templist[:]

If that doesn't work, please post a runnable version of the code to demonstrate the problem. Right now I don't know how to piece your snippets together.

I've solved the problem by rewriting the function using filter():

for i in range(len(num)):

        letters = numdict[int(num[i])]

        namelist = filter(lambda w: w[i] in letters, namelist)

I am still puzzled as to why the previous function I wrote does not work, however. I have done extensive debugging and everything seems fine, except the output. :confused:

EDIT: Ooops, Sane: It looks like you were right. I was still trying to remove from the list I was iterating through... The working function is as follows:

nc = list(namelist)

for i in range(len(num)):

        letters = numdict[int(num[i])]

        for name in nc:

                if name in namelist and name[i] not in letters:

                        namelist.remove(name)

This question can be answered simply by this statement.... *It is Python*

Quote:

Originally Posted by splinter9x

This question can be answered simply by this statement.... *It is Python*

Huh? Of course it's Python...

Are you really that airheaded?

I guess... :o

BTW, why do I have to confirm "name in namelist"? Since nc is a copy of namelist, they should both contain the same names, but I get an error without this check. (Maybe the list contains duplicates? ... but that shouldn't be a problem... should it?)

Wow, it was a joke about the actual language...

Ohhhhhh... I thought you wrote "Is it Python", not "It is Python"... :D

Quote:

Originally Posted by titaniumdecoy

why do I have to confirm "name in namelist"?

Because one of the items may have already been removed by an earlier iteration of _i_. list().remove will raise an error that you could catch if you don't want to check for occurance in the list. The latter should be faster actually (but less understandable).