How to generate "meaningful combinations" from the set of characters?

Question

There is a set of feasible characters, say ABCDEF. Combining some of them, I can generate some "meaningful" combinations, say CAFE. I want to gather all of them.

To do that, I can just "walk through" all possible combinations, starting from length of 2, then 3, until max allowed length, say 5. Then I can check each combination for it's "meaningfulness". But this is inefficient algorithm.

Instead, there is rules that define "meaningfulness". For example, one character couldn't follow after another one, say B after F (contrived example). And vice versa. Some short combinations defines another, more specific rules, etc.

This way I can drastically reduce iterations needed for gathering all possible "meaningful" combinations (looks like).

Is there any well know algorithm for generating combinations in such a way?

Answer 1

You have a dictionary that allows to confirm that a given combination is meaningful. But brute force is too expensive, so you want to optimize the search by pruning the search tree:

• I am not aware of an existing algorithm. If these exist, they would be language dependent.
• Analyzing your dictionary will tell you the impossible combinations. It will also tell you the highly improbable one (but can you risk to ignore them?). The approach is similar to the frequency analysis that cryptanalyst do when they are looking for frequent combination of groups of two or three letters.
• I am afraid however that given the richness of the English language (not even speaking of the Polish language), this approach will not help you to eliminate sufficient combination to get the combinatorial explosion under control.

A more efficient approach could be to predigest the dictionary: for every word, create a search key made of its letters in alphabetic order:

CAFE       -> ACEF
CAFEINE    -> ACEEFIN
FETA       -> AEFT
AFTER      -> AEFRT
NICOTINE   -> CEIINNOT

Then for any letters that you have, you no longer need to check all the combinations, nor even a pruned list of combinations: just sort the candidate letters in the alphabetical order, and check in the dictionary if there's any match.

AEFC      -> ACEF                (alphabetical order)
          -> exact match found:
               ACEF -> CAFE

ORETFA    -> AEFORT              (alphabetical order) 
          -> no exact match 
          -> subsets found: 
               AEFRT -> AFTER
               AEFT  -> FETA 

This is an extremely efficient way to find meaningful combinations. Variants:

• If only exact matches ara allowed, letters would be repeated in dictionary and search key.
• If letters of the candidate are unique and could be repeated, just keep unique letters in dictionary and seach key (e.g. CEINOT instead of CEIINNOT)
• If subsets are allowed, your exploration of dictionary would be slightly more complex. But the normalized order will allow you to search efficiently for subsets.

Answer 2

If you have a list of entities which are meaningful (such as a dictionary of English words), you can do it in the opposite direction: walk through the list and select the words which contain only letters within the range [A-F].

If you don't but you know some rules of what is a meaningful item, you can optimize your code accordingly. For instance, if a consonant is necessarily followed by a vowel, then when during the enumeration, the first letter is D, you know that there are only two choices for the second letter.

If there are no known rules, that is, if you need to do some sort of check to know what is meaningful or not (like doing a HTTP query to Wikipedia to find if an article with the specific name exists), then enumeration is there only way left.