Monday, July 25, 2011

MIT 6.00 Problem Set 6 - Problem 5

LPG Delivery, Seoul

Assume worst case. pick_best_word() is going to produce 13699 candidate words to be checked against the dictionary. pick_best_word_faster() is going to produce 127 candidate words to be checked against the dictionary.

The original word list is length 83667 while the rearranged word list is length 69091. The reduction in length is from the collapse of sets of words made from the same letters into single words.

I think the bulk of the performance improvement is from the reduction in candidate words, not dictionary length or access methods.


Python Output:


>>> len(list(itertools.permutations('abcdefg', 7)))
5040
>>> len(list(itertools.permutations('abcdefg', 6)))
5040
>>> len(list(itertools.permutations('abcdefg', 5)))
2520
>>> len(list(itertools.permutations('abcdefg', 4)))
840
>>> len(list(itertools.permutations('abcdefg', 3)))
210
>>> len(list(itertools.permutations('abcdefg', 2)))
42
>>> len(list(itertools.permutations('abcdefg', 1)))
7
>>> 5040+5040+2520+840+210+42+7
13699

>>> len(list(itertools.combinations('abcdefg', 7)))
1
>>> len(list(itertools.combinations('abcdefg', 6)))
7
>>> len(list(itertools.combinations('abcdefg', 5)))
21
>>> len(list(itertools.combinations('abcdefg', 4)))
35
>>> len(list(itertools.combinations('abcdefg', 3)))
35
>>> len(list(itertools.combinations('abcdefg', 2)))
21
>>> len(list(itertools.combinations('abcdefg', 1)))
7
>>> 1+7+21+35+35+21+7
127

1 comment: