Skip to main content
added 310 characters in body
Source Link
Christophe
  • 80.6k
  • 11
  • 132
  • 199

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 inverse what cryptanalystfrequency analysis that cryptanalyst do when they are looking for frequent combination of groups of two or three lettersgroups 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.

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 the inverse what 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.

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.
Source Link
Christophe
  • 80.6k
  • 11
  • 132
  • 199

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 the inverse what 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.