find words that contains some specific letters

[John B. Matthews]

[snip]
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.

I have to double check but I am actually not sure it is only O(n!)
the reason is that "n" and "m" are two different measures here and
will be wildly different, so I am not sure from the top of my head
that it will be O(n!) taking over rather than O(n! * log m). If the
log was on top of the 'n' yes by all means the factorial would
dominate but not for the 'm'.

I was right, the m is not dominated in this case but the expression:

O(n! * log m)

becomes [1]:

O(n!) * O(log m)

[1] http://www.ugrad.cs.ubc.ca/~cs260/2008W1/chnotes/ch5/Ch5Cov01.html

An excellent summary.

In my dictionary, m = 234936 words and n <= 24. This gives
ln(234936)/(ln(2)) ~ 18 array accesses per lookup, worst cast. Even
doubling m would only increase the worst case by one. Not constant, as I
incorrectly suggested, but a small contribution nonetheless.

The O(n!) term is the killer. In a practical implementation of the
permutation variation (algorithm 2, [1]), I had to limit n, the length
of input words, to no more than 10. Checking 11! = 39916800 permutations
was painfully tedious.

One lesson of the exercise is the value of choosing a better algorithm,
when possible. Algorithm 1 [1] is an example. Constructing the map is
O(m * n log n), and that can be reduced to O(m) by saving the interim
results. Subsequent lookup in the HashMap is O(1).

The largest number of permutations, 11, occurs with "argon" [2]. Sadly,
most of the longest permutations are rather banal:

21 duodenopancreatectomy pancreatoduodenectomy
21 glossolabiopharyngeal labioglossopharyngeal
22 cholecystoduodenostomy duodenocholecystostomy
22 hydropneumopericardium pneumohydropericardium

[1]<http://en.wikipedia.org/wiki/Jumble>
[2]<http://sites.google.com/site/drjohnbmatthews/jumble>