Regex for finding possible words (scrabble-style)

I'm trying to create a "scrabble-solver" to run stress-tests on a scrabble-like game I'm developing. I have a database containing ~200.000 words and I'm now looking for a way to match the scrabble tiles given with the words in the database.

Example:

Given tiles: A, P, E, F, O, L, M

Result: APE, POLE, PALE, MOLE, PAL...

Is this possible by using a simple SELECT-statement with REGEXP? If possible I would also like to add letters on开发者_StackOverflow中文版 specific positions and be able to determine max/min length.

I hope this question made sense :)

I've been googling my eyes out but I can't seem to find what I'm looking for. Anyone got an idea?

Thanks! :)

It doesn't sound like a regex problem. I think you'll be better off simply creating all possible combinations of letters from the existing tiles and then running your SELECT statement with the IN clause. For example, with tiles:

A, P, E

your SELECT clause will be

SELECT word FROM words WHERE word IN ('APE', 'AEP', 'PAE' ,'PEA', 'EPA', 'EAP');

You'll get the list of valid words from your table.

A regex would not help you much in this case. You need to construct the possible words by yourself.

The problem is that you have a limited number of each possible letter and a regex cannot encode that information. If you had infinite supply of each letter, then you could use a regex like [APEFOI]*.

You will have to enumerate all the possible words yourself. The implementation would depend on the language your using, but your best bet might be a next_permutation function or better a function that enumerates all permutations. A simple (and slightly inefficient) implementation (in Python-like pseudocode) would be:

words = []
for permutation in permutations(letters): # enumerate all character orders
  for i in range(1, len(permutation)):    # enumerate all lengths of words
    words.append(letters[:i])             # append to candidate set

At that point words will contain all the candidate words you would then use in a SELECT ... IN statement.

That isn't the most efficient approach, but should be practical enough to get you started.