10 April 2013

Combinatorial Explosion

I think the discussion should have more emphasis in the best practice of using this kind of tool; Just like it is mentioned and used in the MatrixGame & TheLuckyString problems, we need to generate certain rules/filters to optimize the search. To look for all n! possibilities probably never will be a feasible solution. This is also called Combinatorial Explosion which verbatim refers to a growth almost impossible to sustain for the time of this type of TC problems.

So more important than the implementation ( which is assumed know -next_permutation()- that this is called Algorithm L in Knuth's TAOCP 4: it is the good use some criteria for pruning combinations (permutations) and at the end we obtain a reasonable running time.

Many problems use this kind of booby-trap to let the programmer to try to solve with a plenty quick solution which runs over all permutations (or combinations) that finish with a timeout or an unnecessary overhead as resources used (such us memory).

No comments :

My Blog List

Blog Archive


The views expressed on this blog are my own and do not necessarily reflect the views of Oracle.