Anonymous user
Talk:ABC problem: Difference between revisions
→Greedy algorithm: new section
(→Greedy algorithm: new section) |
|||
Line 46:
: There could be duplicate blocks. I didn't mean "set" in the mathematical sense which would be confusing. Collection seems appropriate. --[[User:Jking|Jking]] ([[User talk:Jking|talk]]) 02:55, 9 January 2014 (UTC)
== Greedy algorithm ==
The python iterative solution is greedy and not garanteed to find a solution. Example: if blocks are "AB", "AB", "AC" and "AC", it may fail to find a solution for the word "ABBA". This particular algorithm only works if each letter appears on only one type of blocks. Not finding a solution when there is one is a matter of correctness. Either the task should put further constraints on the blocks ("All blocks containing letter A are of the same letter combinations"), or such algorithms should clearly state the chance of failure ("This is a greedy algorithm that's fast but may fail to find an answer"). --[[User:Ledrug|Ledrug]] ([[User talk:Ledrug|talk]]) 20:12, 10 January 2014 (UTC)
| |||