Question

In PS6, problem 4, we need to check every subset of the letters in HAND against our new dictionary but I'm stumped as to a good way to go through all the subsets of the HAND. It seems simple to go through subsets that are just missing one item but after that the possible subsets are more complicated to keep track of (for me, anyway). I'm sure there's a nice, neat way to go about this and I would love any insight towards it!
Thanks.

Answer 1

i have not actually done that problem set yet..but here is a way i can think of .
how about using nested while and for loops..
like while len(word) <= len (hand)
for i in range (0,len(hand)):
add word =hand[i] to the list
for x in range (0,len(hand)):
word = word + hand[x]
add the word to the list
and something like that...i am not sure..it is just a raw idea...idk it'll work or not.. :(
btw can i get an autograph!!!?? >:D

Answer 2

LOL! Thanks for having faith that my autograph will be worth something some day!

Answer 3

I found an article on Power Sets and it seems like that is the best way to find all the possible subsets. http://en.wikipedia.org/wiki/Power_set
I'm a little surprised that we would need to know how to do something like that when it hasn't been covered in the class or mentioned in the problem set at all. Makes me suspect there is a simpler way and I am just missing it.

Answer 4

I've been stuck on the same problem for like two weeks. I moved on for a while, and I think they do discuss an idea that would help in the following lectures (trees, dynamic programming, and memoization) but I'm still kind of confused. I also just realized my get_word_rearrangements function takes so long that python (or IDLE?) crashes when it tries to run it (I use a Mac and after about 20 seconds I get an unending
"wheel of death") so I'm not sure what's up with that. I've now come back to this problem because in ps8 you need to do something similar, so I guess I've just got to get through it. Help on this would be great though.

Answer 5

i am trying to write a recursive program for that..lets see how it goes :)

Answer 6

and now after seeing Dave's reply i am seriously on it..
u can expect a solution in hours >:D
I am pretty confident u know :p

Answer 7

How did you write your get_word_rearrangements() function? I looked around online and was able to find a pretty decent way to do it. Still doesn't help me with the subsets thing . . .
Take a look at my PS6 if you'd like. I know it's a long file. Sorry. My get_word_rearrangements is right under Problem #1 near the top.

Answer 8

def get_word_rearrangements(word_list):
"""returns a dict of all the rearrangements of the words in word_list"""
global rearrange_dict
rearrange_dict = {}
for w in word_list:
rearrange_dict[''.join(c for c in sorted(w))]=w

Answer 9

I know that last line is crazy-looking. Basically, the ''.join() funtion will combine whatever is in the parens into a string. The sorted() function sorts alphabetically and outputs a list. Sooo . . . this line iterates through each item in the newly sorted list and combines them into a string. That string is used as a key in the dictionary rearrange_dict and is attached to the value w (which is the word I rearranged).

Answer 10

def get_word_rearrangements():
d={}
for w in word_list:
## print d
ws=mergesort(w)
wj=string.join(ws,'')
d[wj]=w

return d


This uses mergesort the way they defined it in one of the lectures around the time this assignment is supposed to be done. mergesort returns a list.

Answer 11

I think mine does the same as yours, vertigo?

Answer 12

It seems like our two function do essentially the same thing. Mine takes less than a second to run, though.

Answer 13

I have no idea why they would be different. Try substituting my code for yours and see if it avoids the spinning beach ball of death. I'm going to try that with yours and see what happens...

Answer 14

is sorted() something you created? or is it in the python library? Also, did I use the word library correctly in the last sentence?

Answer 15

sentence fragment, really.

Answer 16

LOL. It is a built-in python method.
http://wiki.python.org/moin/HowTo/Sorting/

Answer 17

I ran your code, still got the deathball. I'm not sure what's going on now. I know that my code (for all of ps6) is pretty much a mess at this point, which now makes me very sad.

Answer 18

Did you define your own function for mergesort() when I try to run your code it says NameError: global name 'mergesort' is not defined

Answer 19

oh, yes. sorry. here's that stuff. I'll find it on the lecture handout that I got it from too, I guess that might be helpful.

def merge(left,right):
"""Assumes left and right are sorted lists.
Returns a new sorted list containing the same elements
as (left + right) would contain."""
result = []
i,j = 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i = i + 1
else:
result.append(right[j])
j = j + 1
while (i < len(left)):
result.append(left[i])
i = i + 1
while (j < len(right)):
result.append(right[j])
j = j + 1
return result

def mergesort(L):
"""Returns a new sorted list with the same elements as L"""
## print L
if len(L) < 2:
return L[:]
else:
middle = len(L) / 2
left = mergesort(L[:middle])
right = mergesort(L[middle:])
together = merge(left,right)
## print 'merged', together
return together

Answer 20

this is too much

Answer 21

to ask of you. A lot of code. I realize now that I also have slightly different versions of these two things at another place in my file, which could be messing things up (in order to sort based on score for the sake of the 'pick_best_word'). ugh...

Answer 22

Here's a link to the handout, it's from lecture 10. There's really no reason for me to be doing that stuff if it's already a python method. This brings up another, unrelated, question that I have, which is how do you get to know the different built in methods and functions? Just by coding a lot of stuff and looking things up as you go? Just getting kind of stuck and saying to yourself, 'there must already be something to do this, let me check.' ?

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/video-lectures/lecture-10/lec10.pdf

Answer 23

Yeah, i think a lot of stuff (especially from early in the class) was us recreating things that already exist in python or in other standard modules. I spend a lot of time with google open where I type things like 'how do i sort a string in python' and 'how do I find all subsets of a set in python'. There are a lot of good resources out there.
I think the way we learned to do merge and mergesort were pretty basic but not very efficient. For example, our two versions of get_word_rearrangements seem like they do the same thing but I altered the code to show how long each one took to finish and mine took 0.35234322 seconds and yours took 1.3498203 seconds (or something like that). The built-in functions are WAY more efficient.

Answer 24

Yes, I think you're right about all of that.

Answer 25

Hey, I think I did something I shouldn't have. I clicked 'Good Answer' because I wanted to give you some credit for saying productive things and being generally helpful, but now I realize that this kind of tips people off to whether or not a question still needs addressing. I'm not sure if there's a way to undo that, or what. I'm pretty new to this site. Sorry if this is a problem.

Answer 26

And as I promised I am back with the solution >:D
take a look at it :)
http://dpaste.com/hold/576115/

Answer 27

Haha, I just figured out how to get all subsets of HAND. We must have done it at the same time.

Answer 28

whoa. Yours looks a lot better than mine. Itertools...pellet.

Answer 29

this isn't wrapped up into functions yet, and it was only a test, but I think it's obvious how it applies to the problem.

Answer 30

http://dpaste.com/576156/
no imports you haven't learned about yet:)

there is probably a 3 line recursive solution to this problem...

Answer 31

that is a superb piece of code blackarrow :)
though i am yet to learn how the sort() function works :(

Answer 32

i found a recursive solution to this problem on a python forum, and it is indeed very short. I'm still trying to understand it though.

def powerset(seq):
if len(seq):
head = powerset(seq[:-1])
return head + [item + [seq[-1]] for item in head]
else:
return [[]]

Now my problem is that this program (checking whether the word is in any of these substrings) takes about 10 times longer than the original method. Plus the fact that it's O(2^n) doesn't look good at all. I wonder why this is supposed to be the faster method?

Answer 33

for pset6 prob 3 i decided that in order to find the best word you had to try every permutation of hand, taken in varying lengths. this turns out to be a lot of subsets, especially for a large hand. you had to use permutations because the order of the letters in the subset mattered - you have to check the 'ot' subset as well as the 'to' subset to find the word.

in prob 4 you only have to check every combination, taken in varying lengths, - because you have imposed order (sort) on the words you are finding. if you can get sorted subsets then you only have to check 'ot' to find the word. there are a lot less combinations than permutations, especially for big hands.

itertools was a great find - i prefer to use it in a for loop and let it provide each subset as it is needed instead of making a (large) list then using the list then throwing away the list. http://dpaste.com/576462/
lukcily itertools.combinations returns sorted subsets if you provide it with a sorted sequence

http://dpaste.com/576479/

i guess i will take exception to the statement that you can't use something you learned outside of lecture that wasn't presented in lecture.

Answer 34

ok, i get how the recursion posted above works now, please let me know if you need help with the explanation. The only thing I don't get for this problem is how it's supposed be faster than comparing each word in the word list with your unsorted hand, as covered in problem 3. Seems exponential to me.

Answer 35

I agree bwCA...itertools was a great find and finding what works in or out of a lecture is what matters.. ..
Mostly just pulling sunnu's leg and gave him his well deserved medal!

My solution to this problem is actually wasteful if you dissect it. It would return the same answer multiple times if it didn't check if the answer was already there. It works, but is really just a couple of level above brute force in terms of finesse. The itertools solutions is much cleaner. But I always enjoy the process of problem solving rather than finding pre-made solutions....just cause its fun!