# Generating words in given format

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.

• Nice exercise! Where did you encounter this? Can you credit the source of the problem? It sounds like you already have an idea for an approach; why did you reject that approach? What concepts have you been learning recently that might be applicable? Have you heard of a "join" operation, and can you think of any way you might be able to apply it here? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. – D.W. Jun 28 '17 at 23:09
• Hint: Given a fixed "format", there's a concept typically encountered early in formal languages education that can model the predicate, and can be checked efficiently. – Raphael Jun 29 '17 at 5:04
• @D.W. I am working on some classic cryptographic task (cracking some old substitution cipher from 1. world war). I haven't found efficient way to check restrictions. I will try with Prolog programming language, I've never thought i am going to use it in real life. – A J Jun 29 '17 at 7:39
• @Raphael can you be more specific, please ? – A J Jun 29 '17 at 7:46

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.

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: