Question

I am on problem set 6. I have completed all problems up to #4. After having worked on problem #4 I noticed the following oddity:

it is first recommended to make a rearrangement of the dict by implementing get_word_rearrangements() that should return a dictionary which according to pseudocode should contain strings of letters in sorted order as keys and words as values; however, if you think about it two words with different meaning, e.g. different words, can be composed of exactly same letters. After sorting their representations in letters dictionary keys are no longer unique.

Answer 1

Hi @vaboro, I also just finished #4 for ps6. I didn't think about the issue of two words being the same. Gotta check it later though. However, I have a problem with my code. The function pick_best_word_faster is faster than pick_best_word for a hand size 7 and below. However, this does not hold for hand sizes 8 and above. I assume it might have something to with my subsets() function which takes longer to implement as the handsize increases.
Here's my code: http://pastebin.com/hGRtriPa

Answer 2

lines 161 and 162 can be reduced to:
if is_valid_word(word,hand,points_dict):

is valid word could be reduced to http://dpaste.com/756312/

try itertools.combinations() and see if it is faster. with the sorted keys, you only have to check combinations, not permutations
http://docs.python.org/library/itertools.html

Answer 3

@bwCA glad you mentioned the itertools module, yet, as I could get combinations() is not available in itertools of 2.5.4 version used in MIT 6.00 uses
I have already spent many hours trying to write code for producing combinations of letters in a string and would appreciate any help on this

Answer 4

@bwCA but there is the code for combinations() on http://docs.python.org/library/itertools.html, right. However, it took me a while to understand how it works. It is an iterator. It only produces a result if called from within a loop like this:

for i in combinations(string, 2):
print i

Here is the code from itertools help pages (I would really appreciate someone helping me to understand how it works):

def combinations(iterable, r):
# combinations('ABCD', 2) --> AB AC AD BC BD CD
# combinations(range(4), 3) --> 012 013 023 123
pool = tuple(iterable)
n = len(pool)
if r > n:
return
indices = range(r)
yield tuple(pool[i] for i in indices)
while True:
for i in reversed(range(r)):
if indices[i] != i + n - r:
break
else:
return
indices[i] += 1
for j in range(i+1, r):
indices[j] = indices[j-1] + 1
yield tuple(pool[i] for i in indices)

Answer 5

you just have to walk through it to figure it out. here is one i made based on counting in binary: http://dpaste.com/756949/

search for powerset algorithms

Answer 6

I don't know if this will help...here is code I found somewhere online(?!) to produce a powerset without the itertools. I think with a few print statements it's easy enough to follow...
http://pastebin.com/0tm3M9N1