Need help implementing an algorithm in python

gene tani gene.tani at gmail.com
Mon Dec 5 20:39:54 EST 2005


ech0 wrote:
> I would appreciate any help I can get in finding a solution to the
> following problem:
>
> ==================================================================
>
> Below is a diagram:
> http://www.muchographiks.com/algo.jpg
>
> THE PROBLEM
>
> Lets say we have 4 terms (purple represents the terms). Some terms in
> these 4 terms combine to to make keywords (if we get the words in these
> sub-terms they should equal to the keywords (e.g. terms ['kaiser
> chiefs', 'i predict a riot', 'album'] combined make keywords ['kaiser',
> 'chiefs', 'i', 'predict', 'a', 'riot', 'album']). There will be terms
> leftover sometimes, not all terms are used.
>
> POSSIBLE ANSWER?
>
> How it searches for the answer is by combining terms from top to
> bottom, then checking to see if the keywords match the combined terms.
>
> We start by with 1 combination (combine two terms). In the diagram, it
> shows, t1 (term 1) combining with t2 then t3 then t4 (this is the red
> line). If it can't find a match, it continues. It shows t2 combining
> with t3 then t4 (dark green). If it can't find a match, it continues.
> It shows t3 combining with t4 (light green). If by then it can't find a
> match, we do the following:
>
> Now the above example was just 1 combination. It gets more complicated
> because we are going to have to keep increasing the number of
> combinations by 1 to find a match. We are going to keep doing this
> until combinations >= len(keywords). So now its two combinations. t1
> will combine with t2 and t3. Check if its a match. If not continue. t1
> will combine with t3 and t4. check if its a match. t2 will combine with
> t3 and t4. t3 and t4 can't combine by themselves because they are only
> two terms so we skip them (we already did 2 term combinations). After
> this if theres no match we do 3 combinations... all the way until
> combinations >= len(keywords).
>
> ==================================================================
>
> Here is what I have gotten so far:
> http://pastebin.com/450352
>
> I know exactly what to do its just I have no way of translating the
> thought into programming code. If anybody can help at all I would
> greatly appreciate it.
> 
> Thanks.

Be honest, is this a take-home final ?




More information about the Python-list mailing list