2

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?

  • 3
    Do you have a definite definition of what counts as "meaningful" or not? If you do, generating all combinations and applying the check is almost certainly efficient enough - no need to invent a custom generator that skips some candidates. If you don't, then you can't really solve this on a computer at all. – Kilian Foth Dec 22 '19 at 21:19
  • I mostly agree with Kilian, however, if your definition of "meaningful" is "I know it when I see it", you can use some methods from artificial intelligence and machine learning. In particular, you could train a neural network with reinforcement learning to recognize "meaningful". Although for this particular case I would expect overfitting (the neural network takes more memory than the data), yet the exercise could help you discover what exactly do you mean by "meaningful". – Theraot Dec 22 '19 at 23:18
  • @KilianFoth I understand the sentence "I can check each combination for it's meaningfulness" as an indication that we do not have to care for this part. OP probably has a dictionary of valid words. – Christophe Dec 22 '19 at 23:53
  • @KilianFoth Recently I realized that there is actually two things. One that if there is clear definition of "meaningfulness". For example, a dictionary. This is mostly answered in Christophe's answer. Another is that there is none. It's basically "I know it when I see it", as of Theraot. All possible "meaningful things" go far beyond know at this present moment. And recommended way of training neural network looks like very interesting exercise. – tosh Dec 24 '19 at 19:07
4

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.
| improve this answer | |
  • Do you mean that instead of checking each of CAFE, CAEF, CFAE, CFEA, CEAF, CEFA, ACFE, ACEF, AFCE, AFEC, AECF, AEFC, FCAE, FCEA, FACE, FAEC, FECA, FEAC, ECAF, ECFA, EACF, EAFC, EFCA, EFAC I can check just one ACEF? (I think it is) If so, then I steel didn't grasp, how should I eventually reach ACEF itself from all possibilites? Sorry if I speak vaguely. – tosh Dec 24 '19 at 18:55
  • @tosh In your approach when you want to eliminate some combinations such as CBXE. Her it goes further sine you could eliminate any combination such as AFCE that does not have its letters in the alphabetical order. You may make the combinatorial maths: how much possible combinations vs. how much combination that are alphabetically sorted. – Christophe Dec 24 '19 at 19:42
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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.