Generating words in given format

Question

i am looking for an algorithm that will generate all possible combinations of words from given dictionary that satisfy given format.

Let me explain what i mean with format:

For example, if the format is "abcd" means that we are looking for one word, length of the word must be 4 and because all the letters in format are different, all the letters in the word must be different.

The format "computer science" means:

1) We are looking for 2 words (one of length len("computer") = 8 and one of lenght len("science") = 7)

2) The first char of the first word must be the same as the second char and the sixth char in the second word (letter "c" in format)

3) The seventh char of the first word must be the same as the the forth and the last char in the second word (letter "e" in format)

Is it better to generate all the possible strings in given format and the look them up in the dictionary or somehow build strings using dictionary ?

edit:

My idea:

1) split big dictionary (100 millions of words) into smaller ones based on word length.

2) for first word get trough all the entries in particular dictionary and try to match first word, then continue with the next one, but with more restrictions.

Thank you for your help!

Answer 1

This can be solved with a join operation.

Let's take your example with format "computer science":

• Build one list L1 of dictionary words where each word is mapped to a two-letter key, by extracting the first and seventh letter of the word.

• Build a second list L2 of dictionary words where each word is mapped to a two-letter key, by extracting the second and fourth letter of the word; with the additional restriction that you only include words where the 2nd and 6th letter are the same, and where the 4th and 7th letter are the same.

• Now compute the "join" of L1 and L2, i.e., where you look for all pairs of a word from L1 and a word from L2 that have the same key. This can be done by any of the standard join algorithm, e.g., a hash join or a sort-merge join.

You should be able to see how to generalize this to arbitrary formats, possibly by performing multiple join operations (if the format has three or more words). If you need to perform multiple join operations, there are multiple different orders in which you can perform the join operations; the topic of query optimization deals with how to choose the best order.

Answer 2

Alright, I managed to solve this problem using Prolog.

First of all, I've converted wordlist.txt from:

• word1
• word2
• ...

Into wordlist.pl:

• w(w,o,r,d,1).
• w(w,o,r,d,2).

Then I've found Prolog function, that tells me if all the elements in the list are different:

alldif([]).
alldif([E|Es]) :-
   maplist(dif(E), Es),
   alldif(Es).

After that I have written Prolog function, that takes predefined format and finds all the possible words from dictionary, that meet given format:

g(Format, String):-
    list_to_set(Format, Uniques),
    alldif(Uniques),
    w(Format),
    atomic_list_concat(Format, '', Atom), atom_string(Atom, String).

Now I'm able to call:

g([A,B,C], String1), g([A,D,A], String2).

That generates me all possible combinations of String1 and string2 with following format:

"ABC ADA"