Question

In problem set 3 part B - is comp_choose_word
supposed to take a REALLY long time to find the highest scoring permutation that exists in the word_list?

Answer 1

Running this function in a test harness through a shell in linux, and using the following values for hand size: [1,2,3,4,5,6,7], I got these values for the time to compute the highest scoring valid word from all permutations: [0.105s, 0.106s, 0.167s, 0.255s, 0.906s, 8.252s, 51.313s] - its clear that my implementation is complexity > O(n), but should it be?

Answer 2

to find search for the current permutation being tested in the word_list im using:

if word in word_list:
###calculate word score and compare with current highest score

where word is a string
Since the word_list is sorted, maybe a binary search would be faster than the if-in search?
maybe that would reduce complexity from O(n**2) to O(nlogn)???
Online T.A.'s - any insight?

Answer 3

Here's the search with the outer loop its contained in:

for word in perms:
if word in word_list:
###compute word score and compare to highest score so far...

where perms is a list containing all permutations from 1 to n lettters long of the given hand

Answer 4

you can post your code using a code pasting site like dpaste.com

Answer 5

thanks ill keep that in mind if i wanna post more than one line

Answer 6

you can improve the search using a binary search but you are still stuck with the subset growth rate as hand size increases
...
http://dpaste.com/778986/