Programming Forums > Script Programming > Python

titaniumdecoy · Jun 8th, 2006, 10:41 PM

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:

(Toggle Plain Text)

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?

(Toggle Plain Text)

# 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:

(Toggle Plain Text)

# 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.

Sane · Jun 8th, 2006, 10:46 PM

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:

(Toggle Plain Text)

# 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.

titaniumdecoy · Jun 8th, 2006, 11:14 PM

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

(Toggle Plain Text)

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.

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:

(Toggle Plain Text)

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)

splinter9x · Jun 8th, 2006, 11:21 PM

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

titaniumdecoy · Jun 8th, 2006, 11:23 PM

Quote:

Originally Posted by splinter9x

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

Huh? Of course it's Python...

splinter9x · Jun 8th, 2006, 11:24 PM

Are you really that airheaded?

titaniumdecoy · Jun 8th, 2006, 11:24 PM

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?)

splinter9x · Jun 8th, 2006, 11:26 PM

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

titaniumdecoy · Jun 8th, 2006, 11:32 PM

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

Sane · Jun 8th, 2006, 11:40 PM

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).

Jun 8th, 2006, 10:41 PM	#1
titaniumdecoy Programming Guru Join Date: Nov 2005 Posts: 1,007 Rep Power: 5	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: (Toggle Plain Text) 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'] 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? (Toggle Plain Text) # 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 # 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: (Toggle Plain Text) # 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) # 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.

Jun 8th, 2006, 10:46 PM	#2
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 2,188 Rep Power: 6	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: (Toggle Plain Text) # 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[:] # 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.

Jun 8th, 2006, 11:14 PM	#3
titaniumdecoy Programming Guru Join Date: Nov 2005 Posts: 1,007 Rep Power: 5	I've solved the problem by rewriting the function using filter(): (Toggle Plain Text) for i in range(len(num)): letters = numdict[int(num[i])] namelist = filter(lambda w: w[i] in letters, namelist) 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. 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: (Toggle Plain Text) 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) 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)

Jun 8th, 2006, 11:21 PM	#4
splinter9x Hobbyist Programmer Join Date: Jun 2006 Posts: 137 Rep Power: 0	This question can be answered simply by this statement.... It is Python __________________ Visit my Blog I support WINDOWS...

Jun 8th, 2006, 11:24 PM	#6
splinter9x Hobbyist Programmer Join Date: Jun 2006 Posts: 137 Rep Power: 0	Are you really that airheaded? __________________ Visit my Blog I support WINDOWS...

Jun 8th, 2006, 11:26 PM	#8
splinter9x Hobbyist Programmer Join Date: Jun 2006 Posts: 137 Rep Power: 0	Wow, it was a joke about the actual language... __________________ Visit my Blog I support WINDOWS...

Jun 8th, 2006, 11:32 PM	#9
titaniumdecoy Programming Guru Join Date: Nov 2005 Posts: 1,007 Rep Power: 5	Ohhhhhh... I thought you wrote "Is it Python", not "It is Python"...

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Programming Forums > Script Programming > Python

What's wrong with this code?