On 1/7/07, Fedor Labounko <fedor.labounko / gmail.com> wrote:
> On 1/7/07, Daniel Finnie <danfinnie / optonline.net> wrote:
>
> > # Find words that use the same letters
> > selectedWords = dict.scan(/^[#{baseWord}]{3,6}$/)
>
>
> I was really impressed when I first saw this. It doesn't quite work if you
> want to exclude reusing the same letter more than once
> ("hhh".scan(/^[hello]{3,6}$/) => ["hhh"]) but it comes so close to something
> I've only ever thought about implementing as a recursive method.
> Unfortunately I don't know much about this but now I wonder if it's possible
> to find all partial permutations of a word with a regexp.
>
>

Here's a revision to Daniel's approach that seems to work well:

# Open and read the dictionary.
dict = IO.read("/usr/share/dict/words").scan(/^[a-z]{3,6}$/)

# Pick a random word with 6 letters.
baseWord = dict.grep(/^[a-z]{6}$/).rand_elem

# Find words that use the same letters
sortWord = baseWord.scan(/./).sort.to_s
selectedWords = dict.select {|w|
Regexp.new(w.scan(/./).sort.join('.*')).match(sortWord) }

I started by just extracting only the 3-6 letter words.

Then I sort the base word so the letters are in order. Let's say the
baseWord is "parlor". Then sortWord would be "aloprr".

Now for each word in the dictionary, sort it in letter order and
create a regex. Suppose the word is "roar". The sorted version is
"aorr" and the regex is "a.*o.*r.*r". If that regex matches the
sortWord, we found a valid subword.

This could be sped up by precompiling the regexes I would guess.

Bob