Perl Monk, Perl Meditation  
PerlMonks 
Re^10: Challenge: 8 Letters, Most Wordsby LanX (Chancellor) 
on Oct 06, 2013 at 12:26 UTC ( #1057142=note: print w/replies, xml )  Need Help?? 
hi Limbic~Region IMHO all "heuristic" methods must have flows... I'm quite experienced with these kind of problems and people tend to underestimate them (I'm not smart just trained :). And shouldn't be to difficult to show this belongs to NPclass. Anyway since I was able to calculate all possible 8lettercombinations within 3 minutes with an nonoptimized recursion it should be possible to find an approach to rapidly calculate each coveringnumber and to choose the maximum. Let me explain: First of all a good branchandbound could avoid useless branches which can't possibly beat the current maximum (my recursion just needs more criteria to bound) (this doesn't contradict NP, NP is about runtime and not correctness)² In order to speed up calculation, one should cache subsolutions which can be rapidly added. Let l be a lettercombination to be checked and L^{x} all derived combinations by striking x letters and n(l) the number of dictionarywords which can be formed with exactly all letters. its easy to see that the covering C(l)= n(l)+ sum { C($_) } L^{1}  sum { C($_) } L^{2} e.g. C('abc') = n('abc') + C('ab')+C('ac')+C('bc')  C(a) C(b)C(c) and with the table from this post ¹
we see C('abc') = 0+3+2+2(1+1+0) = 5 and indeed the first 5 entries in the table can be constructed out of a,b and c! So to calculate the covering of an 8letter tuple we just need to look up the covering of (at most) 8 7letter subtuples and 28 6letter subtuples and add them. Starting with all 1letter tuples one can successively calculate the covering of all 2letter tuples and so on.
Holding 16 million hashentries shouldn't be a problem. A worst case of 591_937_740 (=16442715 *(28+8)) additions neither, which are already 1000 times less operations than in your C program. This should be fast enough for 8 letters and I doubt one can do it faster...³ Implementation left as an exercise! :) Cheers Rolf ( addicted to the Perl Programming Language) ¹) for simplification this table only holds ordered words, extending it to count different permutations of the same letters ("cab" and "abc" => n("abc") =2 ) wouldn't change the math! ²) and normally one can always construct an edge case where the recursion never bounds. ³) please note the complexity rises exponentially for more letters, it's still NP!
In Section
Seekers of Perl Wisdom

