Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer

Re: challanging the dictionary

by blokhead (Monsignor)
on Apr 27, 2004 at 16:05 UTC ( #348555=note: print w/replies, xml ) Need Help??

in reply to challenging the dictionary

Good luck, this is exactly the NP-complete Minimum Set Cover problem (which makes me hope it's not homework). The universe is the set of letters, the family of subsets is the dictionary of words. You want to minimize the number of words needed to use all the letters in the alphabet, in other words, the number of subsets needed such that each element in the universe is contained in at least one chosen subset.

You won't be able to do significantly better than brute force, unless an approximation algorithm would also be appropriate for your needs. But with a huge dictionary, the running time is going to be intractable.


Replies are listed 'Best First'.
Re^2: challanging the dictionary
by Limbic~Region (Chancellor) on Apr 23, 2006 at 23:11 UTC
    This seems to be a relatively fast approximation algorithm (64K words in about 5 seconds):

    The algorithm is quite simple. Start with the rarest letter and look for words containing that letter that have the most unique letters not found so far. Wash-Rinse-Repeat.

    Cheers - L~R

Re^2: challanging the dictionary
by Limbic~Region (Chancellor) on Oct 25, 2006 at 14:28 UTC
    Good luck,...

    Thanks, I am sure I will need a bit of that.

    But with a huge dictionary, the running time is going to be intractable.

    Well fortunately for humans, alphabets are relatively small and very long words that do not repeat letters are uncommon. The number of words that you need consider from a huge (~ 65K words) is quite manageable. See How many words does it take? for an example.

    Cheers - L~R

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://348555]
[shmem]: LanX: now I have to find a succinct transformation FOOL => MONK
[LanX]: yeah but Marto already proposed a new "Lex Sun-D" ...
[karlgoethebier]: the word really exists: http://www. urbandictionary. com/define.php? term=fool
[shmem]: ...possibly involving RTFM
[karlgoethebier]: big surprise!
[Eily]: LanX I try to avoid answering, but I did feel that this one post was going into much detail to prove a false claim (that SHA-1 is secure, I was just wrong about how insecure it is)
[LanX]: ironically...
[LanX]: yeah whatever ... I'm in the favorable condition to already autohiding him ... how can I judge the poor FOOLs who still see his contributions xD
[Eily]: he's been pretty saavy about threads that were implictly about him in the past. I think he might have deliberatly avoiding mentioning it for some reason (he got tired?)
[Eily]: he did mention one of his propositions: basically make it possible to ignore downvotes, by separating them more from the upvotes

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (8)
As of 2017-07-24 17:21 GMT
Find Nodes?
    Voting Booth?
    I came, I saw, I ...

    Results (356 votes). Check out past polls.