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

[download]

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

[download]

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!

In reply to Re^10: Challenge: 8 Letters, Most Words by LanX
in thread Challenge: 8 Letters, Most Words by Limbic~Region

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.