How to find all words with any permutation of the given letters in SQL?

Question

I am working with the sqlite3 module, using Python 3.10.0. I have created a database with a table of English words, where one of the columns is creatively named "word". My question is, how can I sample all the words that contain at most the letters within the given word? For example, if the input was "establishment", valid outputs could be "meant", "tame", "mate", "team", "establish", "neat", and so on. Invalid inputs consist of words with any other letters other than those found within the input. I have done some research on this, but the only thing I found which even comes close to this is using the LIKE keyword, which seems to be a limited version of regular expression matching. I mentioned using Python 3.10 because I think I read somewhere that sqlite3 supports user-defined functions, but I figured I'd ask first to see if somebody knows an easier solution.

Answer 1

Your question is extremely vague.

---

Let me answer a related question: "How may I efficiently find anagrams of a given word?"

There is a standard approach to this. Simply alphabetize all letters within a word, and store them in sorted order.

So given a dictionary containing these "known" words, we would have the first three map to the same string:

• pale <--> aelp
• peal <--> aelp
• plea <--> aelp
• plan <--> alnp

Now given a query word of "leap", how shall we efficiently find its anagrams?

1. Turn it into "aelp".
2. Query for that string, retrieving three matching dictionary words.

Sqlite is an excellent fit for such a task. It can easily produce suitable column indexes.

---

Now let's return to your problem. I suspect it's a bit more complex than anagrams. Consider using a related approach.

Rip through each dictionary word, storing digrams in standard order. So for "pale", we would store:

• pale <--> ap
• pale <--> al
• pale <--> el

Repeat for all other dictionary words.

Then, at query time, given an input of "leap", you might consult the database for "el", "ae", and "ap".

Notice that "ae" missed, there. If that troubles you, when processing the whole dictionary feel free to store all 2-letter combinations, even ones that aren't consecutive.

Possibly going to trigrams, or all 3-letter combinations, would prove helpful. Spend some time working with the problem to find out.