Question

ps#6, problem 4, can anyone help me in proper implementation of pick_best_word_faster() ? i'm having problem in making multisets of letters from given dict, where letter is a key and value is number of this letters left in hand. thanks in advance

Answer 1

http://dpaste.com/709255/

Answer 2

Thank you for your reply, i've already seen something like that before on the web ,and i've tried some of those already, but as for ps 6 (which actually was given after lecture about divide and conquer methods),as intended in the course program, i don't mean to know anything about lambdas and itertools so far. The problem with original (combo) solution is that it's complexity is \[O(2^{n})\] thougn we need ro find a solution faster than \[O(n ^{2})\]

Answer 3

And as for original solution - I am not supposed to know about yield so far

Answer 4

well there is a lot about the Python language that is never mentioned or taught in the class. do you suppose that they expect you not to read for yourself and seek out the information you need then use that knowledge? this is an introductory class on computer science and programming (concepts) - being given to people who chose to be there and are expected to be resourceful and use their initiative. this is NOT a course in Python - they chose Python as the language used to illustrate what they want you to learn because Python seems to be an easy-to-learn first language.

there are some of very good wikipedia articles on combinations and permutations.
given that the algorithm will be producing combinations of varying lengths i'm not sure that there is any way to thwart the math - there is a finite number of 'combinations taken k at a time' and that number depends on the length of the original thing. if you do not produce all of those subsets, you risk not finding the best word so you are stuck with 2**n

granted that writing a combination generator from scratch or figuring out how one (that you found elsewhere) works is tuff; i believe that is not the lesson they are trying to teach.

Answer 5

here are some posted here by others
tsbpig - http://dpaste.com/709402/
007 - http://dpaste.com/709404/
djones - http://dpaste.com/709406/

Answer 6

Thank you for you reply again. I understand that 6.00 is not about Python, but I still think that learning about generators by students themselves is not a good idea, because that is really hard topic, given that students may not have any programming experience. I believe that by giving such assignment to online auditory, tutors could intend some additional reading and exploration, but that definetely doesn't mean to learn difficult part of language.

That is why I tend to think that there may be some kind of solution with techniques, already learnt in lectures, provided reading sections and some reasonable amount of independent work.

The main question is - how can exponential algorithm (which is only one i can figure out til now) be faster than quadratic algorithm? I understand that I need any subset of a given hand, e.g for 'abcd' i will need al those: 'ab', 'ad', 'bd', 'abd' and many more

Answer 7

i think the other three links i posted only used parts of the language taught up to that point in the course

this is what i got out of it. without the rearrange dictionary, the letter positions for the words are basically random. so if you have three letters that you want to make a word out of you have to check abd, adb, dab, bda to ensure you don't miss something - those are permutations. with the re-arrange dictionary you only have to match a sorted three letter string, which there is only one abd - that is the only combination of those three letters.

the number of combinations of n taken k at a time for all k is 2^n
the number of permutationss of n taken k at a time for all k is much more and grows at a different rate.

http://ideone.com/cBzcE

Answer 8

I don't think it is possible to get a solution faster than O(2^n) for pick_best_word_faster because you have n letters and each one is in one of two positions. You need to output every possible subset, so you much have at least 2^n operations. However, it is still faster than the O(n) pick_best_word because the n's are different. In pick_best_word then n is the word_list whereas in pick_best_word_faster the n is the size of the hand. Since word_list is so much larger than hand, pick_best_word_faster is much much faster than pick_best_word. Implement it and give it a try.