Question

I ps6 problem #4, how can/should the subsets of a hand be generated for the pick_best_word_faster function. If all the subsets are generated, what is the purpose of the get_word_rearrangements function?

Answer 1

I think the most difficult part by far is to generate all the hand subsets. I struggled a lot with that part. Each hand subset has to have its letters sorted in order of points. Once you have all the ordered hand subsets just look for them in the rearrangeDict and pick the one that has the highest score. Once you have the pick_best_word_faster create a small test code to compare the results of pick_best_word_faster to pick_best_word. For a given hand they might not select the same word but the score should be the same.

I think the idea is that by going to the trouble of creating a rearranged dictionary and generating all the ordered hand subsets then things will go faster. The problem is that generating all the hand subsets is computer intensive and at least for me dealing with hands of length 8 or longer the pick_best_word function is actually faster. For hands of 7 or less pick_best_word_faster is *much* faster, though.

Answer 2

pick best word faster only has to create all the combinations whereas pick_best_word needed all the permutations - there is a pretty big difference and they grow at different rates

Answer 3

So as the length of the hand grows pick_best_word_faster should be faster than pick_best_word?

Answer 4

bwCA, would appreciate your insight a lot. Maybe I am wrong, for the pick_best_word function I did not generate any combinations. First I created a small function that checks if a word can be made using the letters from the hand. Then I loop through the whole dictionary. For each dictionary word I checked whether the word can be made using the letters from the hand. If it can, then I check the score using the wordsToPointsDict, whichever word was the highest score is the one. Runs fast.

For hand size <=7 pick_best_word_faster was indeed faster but for hand size >7 pick_best_word is faster. Did you find any good resources that gave you insight on how to generate combinations and permutations from the hand letters?? I really struggled with that.

Answer 5

carlosgg, I agree. I didn't generate anything for pick_best_word. The function just compares the number of letters in a word with the number of letters in the hand.

The python module itertools can generate both combinations and permutations, but I remember this module being mentioned in the related reading or lecture. I also don't remember any mention about how to create combinations or permutations so in the interest of time, I'll probably use the itertools module as the focus of this exercise is to determine Order of Growth. Thank you both for the replies.

Answer 6

No problem. I had never heard of itertools before, thank you. Once you solve it please post your conclusion (part 5 of the problem) on this same thread.

Answer 7

yep, seems i did it the hard way (pick-best-word)

the number of combinations and permutations grow at different rates for the hand size
(pretty sure that is correct)

i used the itertools module

Answer 8

Good to know thanks for sharing. I will check out itertools. Where did you learn about it?

Answer 9

I googled "python permutations," and the first result was:
http://docs.python.org/library/itertools.html

Answer 10

:) Thanks!

Answer 11

After getting a little further, I've realized that since the subsets should all be sorted alphabetically, only combinations (not permutations) are required, and with a HAND_SIZE of 7, 127 subsets are possible. If including a null set then 128 (2 raised to the power of HAND_SIZE) are possible.

Answer 12

yes - with 'unsorted comparisons' it requires permutations (order matters) and with the 'sorted comparisons' on the combinations (order doesn't matter) are required. Fortunately the itertools methods return sorted subsets.