Re: find words that contains some specific letters

In article <78i4i2F1magkfU1@xxxxxxxxxxxxxxxxxx>,
"Giovanni Azua" <bravegag@xxxxxxxxxxx> wrote:

Hi Lew,

"Lew" <noone@xxxxxxxxxxxxx> wrote in message
I found it here "Stirling's approximation"
<http://en.wikipedia.org/wiki/Factorial#Rate_of_growth>

so it would be o(n! * log2 m) => O(n^n * log m) and this is NP ...

You only build the Set of permuted letters once. Then, following John

Once per search to be precise.

Matthews's suggestion to which you replied, you look up the n!
permutations with an O(1) lookup in the Set of dictionary words.
So the actual complexity is just O(n!)

One word lookup in the Set costs O(log m) binary search and not O(1).
Therefore the O(log m) is *for each* generated permutation, and this is
why the multiplication i.e. O(n! * log m)

Thank you both for elucidating this. If I understand big O notation
correctly, the factorial term dominates the complexity, giving O(n!)
overall. Of course, I would welcome clarification.

Or one build the dictionary as a Map indexed by word letters in
alphabetical order with the values being corresponding Sets of
words using those letters. Then you only do an O(1) lookup into the
Map to find the single ordered permutation of the search term, then
return the matching Set directly. So now the overall lookup
complexity is that of sorting the letters in the search term.

Indeed, my approach is fine for small permutations (e.g. word puzzles,
password strength), but hashing on the sorted letters of the dictionary
entries beforehand gives what a appears to be an O(n log n) algorithm:

<http://en.wikipedia.org/wiki/Jumble>

--
John B. Matthews
trashgod at gmail dot com
<http://sites.google.com/site/drjohnbmatthews>
.

Relevant Pages

  • Re: Combinatorics question
    ... >> specific set of letters. ... Within a bin, a ... > Your bin is modeled by a mathematical object called a multiset. ... > If you order the objects, you can deal with permutations of the set ...
    (sci.math)
  • Re: Combinatorics
    ... combinations (with and without repetition) ... but the standard combinatorics (replacement ... (permutations with replacement) ...
    (comp.lang.python)
  • Re: Reading in a Dictionary File
    ... Not necessarily a BufferedReader. ... calculate the permutations of the letters, and then try to match them ... Creating permutations and looking them up probably isn't such a good idea ... Using a trie, it can be much easier to start with the few ...
    (comp.lang.java.help)
  • Re: Combinatorics question
    ... > specific set of letters. ... Within a bin, a ... Your bin is modeled by a mathematical object called a multiset. ... you can deal with permutations of the set ...
    (sci.math)
  • Re: find words that contains some specific letters
    ... I remember in class we used to evaluate complexity using the O notation with exponential function rather than n! ... You only build the Set of permuted letters once. ... permutations with an Olookup in the Set of dictionary words. ... Then you only do an Olookup into the Map to find the single ordered permutation of the search term, then return the matching Set directly. ...
    (comp.lang.java.programmer)