Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

Re^10: Challenge: 8 Letters, Most Words

by LanX (Canon)
on Oct 06, 2013 at 12:26 UTC ( #1057142=note: print w/ replies, xml ) Need Help??


in reply to Re^9: Challenge: 8 Letters, Most Words
in thread Challenge: 8 Letters, Most Words

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 NP-class.

Anyway since I was able to calculate all possible 8-letter-combinations within 3 minutes with an non-optimized recursion it should be possible to find an approach to rapidly calculate each covering-number and to choose the maximum.

Let me explain:

First of all a good branch-and-bound 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 run-time and not correctness)

In order to speed up calculation, one should cache sub-solutions which can be rapidly added.

Let l be a letter-combination to be checked and L-x all derived combinations by striking x letters and n(l) the number of dictionary-words 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

1 a 1 b 3 a b 2 a c 2 b c 4 a b d

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 8-letter tuple we just need to look up the covering of (at most) 8 7-letter sub-tuples and 28 6-letter sub-tuples and add them.

Starting with all 1-letter tuples one can successively calculate the covering of all 2-letter tuples and so on.

-max: 1 26 -max: 2 350 -max: 3 3247 -max: 4 23312 -max: 5 137909 -max: 6 698996 -max: 7 3116882 -max: 8 12461993 sum 16442715

Holding 16 million hash-entries 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!


Comment on Re^10: Challenge: 8 Letters, Most Words
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1057142]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (18)
As of 2015-07-28 19:25 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (258 votes), past polls