regular expressions: matching all words containing a specific list of letters

Question

The regular expression \ws\|l\|d matches all words containing at least one of the letters s, l and d. What is the correct syntax to match all words containing all these letters? (like solid, dollars, etc).

I found the following cheat sheet on http://www.emacswiki.org/emacs/RegularExpression but I cannot find the AND operation.

  .        any character (but newline)
  *        previous character or group, repeated 0 or more time
  +        previous character or group, repeated 1 or more time
  ?        previous character or group, repeated 0 or 1 time  
  ^        start of line
  $        end of line
  [...]    any character between brackets
  [^..]    any character not in the brackets
  [a-z]    any character between a and z
  \        prevents interpretation of following special char
  \|       or
  \w       word constituent
  \b       word boundary
  \sc      character with c syntax (e.g. \s- for whitespace char)
  \( \)    start\end of group
  \< \>    start\end of word
  \_< \_>  start\end of symbol
  \` \'    start\end of buffer\string
  \1       string matched by the first group
  \n       string matched by the nth group
  \{3\}    previous character or group, repeated 3 times
  \{3,\}   previous character or group, repeated 3 or more times
  \{3,6\}  previous character or group, repeated 3 to 6 times
  \=       match succeeds if it is located at point

  \ca      ascii character
  \Ca      non-ascii character (newline included)
  \cl      latin character
  \cg      greek character

  [:digit:]  a digit, same as [0-9]
  [:alpha:]  a letter (an alphabetic character)
  [:alnum:]  a letter or adigit (an alphanumeric character ()
  [:upper:]  a letter in uppercase
  [:space:]  a whitespace character, as defined by the syntax table
  [:xdigit:] an hexadecimal digit
  [:cntrl:]  a control character
  [:ascii:]  an ascii character

  \s-   whitespace character        \s/   character quote character
  \sw   word constituent            \s$   paired delimiter         
  \s_   symbol constituent          \s'   expression prefix        
  \s.   punctuation character       \s<   comment starter          
  \s(   open delimiter character    \s>   comment ender            
  \s)   close delimiter character   \s!   generic comment delimiter
  \s"   string quote character      \s|   generic string delimiter 
  \s\   escape character            

Answer 1

You're looking for something that can be found by a regexp (a word), but which should additionally obey some constraint.

In this case the constraint is a form of subset-relation:

(defun string-subset-p (s1 s2)
  "Return t, if S1 is a subset of S2, when viewed as char-sets."
  (let ((s2-chars (append s2 nil)))
    (cl-every (lambda (ch)
                (memq ch s2-chars))
              (append s1 nil))))

When put together (in the most trivial way):

(defun search-word-containg-chars-forward (chars)
  (interactive "sChars: ")
  (while (and (re-search-forward "\\w+")
              (not (string-subset-p chars (match-string 0))))))

More efficient implementations for the string-subset-p function are left as an exercise to the reader. Though, chances are, that it won't really matter.

Answer 2

Here's one way to implement some equivalent to the "AND"ing of regexp needed for this specific application.

The word at point is first character sorted so that dollars becomes adllors in a temporary buffer. That temporary sorted string is then matched with occurrence of any optional alphabet followed by d, followed by any optional alphabet followed by l, followed by any optional alphabet followed by s, followed by any optional alphabet. If that match is true, the word is highlighted, else a message is displayed.

To do this over the whole buffer, do M-x my/match-word-whole-buffer.

(defun my/match-word ()
  "Matches words containing all chars d, l, s in any order: dollars solid 
Match will fail if a word is missing any of those characters. e.g. dollar"
  (interactive)
  (let ((this-word (thing-at-point 'word)); get the word at point
        (match))
    (with-temp-buffer
      (insert this-word)
      (sort-regexp-fields nil "\\w" "\\&" (point-min) (point-max)) ; sort chars in word
      (beginning-of-buffer)
      ;; Now that the chars are sorted alphabetically, you can search for
      ;; the letters in alphabetical order: d, l, s
      (if (looking-at "\\w*[d]+\\w*[l]+\\w*[s]+\\w*")
          (setq match t)
        (setq match nil)))
    (when match
      (highlight-symbol-at-point))))

(defun my/match-word-whole-buffer ()
  (interactive)
  (beginning-of-buffer)
  (forward-word)
  (while (not (eobp))
    (when (string-match "\\w\\{3,\\}" (thing-at-point 'word))
      (my/match-word))
    (forward-word)))

Answer 3

There is no "and" operation in regexps. You'd have to write a regexp with six alternatives for the possible orders:

• words containing S, L and D
• words containing S, D and L
• words containing L, S and D
• words containing L, D and S
• words containing D, L and S
• words containing D, S and L

Answer 4

If you are OK with calling grep from Emacs for what you need then the expression could look like this:

for i in dollars dollar solid; 
do
  echo "$i" | grep -P '\b\w*(?=\w*l)(?=\w*d)(?=\w*s)\w*\b'
done;

gives:

dollars
solid

You could, in Emacs, select the interesting region and then M-| - this will prompt you for the command to run on the region, and then you could enter the regexp above.

If the regexp looks puzzling, the idea is that when lookahead (the ?= part) matches it doesn't advance the parser, so it can match multiple times when looking ahead from the same place without consuming any input.

Answer 5

You say that you "have a file containing a list of all words of a language" and you "would like to find all words containing some letters (in any order)." Do you want to search the file interactively or by program?

If interactive, consider using Icicles search, progressively matching each letter - the order does not matter.

For example: C-c ` \w+ RET tells icicle-search (bond to C-c `) to use words as the search contexts, meaning search only within words.

Then type the letters to match within each word, separating them by S-SPC. For example, to match letters h, t, and e in the same word, you can type h S-SPC t S-SPC e (or the same letters in any order). The use of S-SPC says to match each pattern that it separates (in this case, single letters), progressively narrowing the matches from the previous match.

C-c ` \w+ RET h S-TAB S-SPC t S-SPC e

Matches are shown after you use S-TAB or TAB (or automatically, if option icicle-show-Completions-initially-flag is non-nil). If you use S-TAB before typing any input to match then the matches for empty input are shown immediately, and they include all of the text in each search context - in this case, all of the words.

S-TAB tells Icicles to use apropos matching, not prefix matching. In the example above, it is used after typing h, which means that you want to match h anywhere within the context (word), not just at its beginning (as a prefix). (S-SPC always uses apropos matching for the following input.)

The default matching mode (apropos or prefix) is controlled by option icicle-default-cycling-mode. The default value of the option is prefix matching. If you customize it to apropos instead, then the explicit S-TAB mentioned above is not needed: you get apropos matching by default.