Ever had the problem that you are searching for something containing both foo and bar? If you use a RegularExpression for that, the simple expressions are either foo.*bar or bar.*foo. This page presents code that lets you search for “foo, bar” and constructs a regexp that matches both combinations. This is useful when searching for a symbol name using apropos, for example.
See Also: Icicles - Search Commands, Overview. If you use Icicles, then you can search for terms such as
‘bar’ in any order. What’s more, Icicles - Progressive Completion lets you apply the same technique to any MiniBuffer Completion: match, for instance, a command name or a buffer name or a file name that contains both
‘bar’ in any order.
First, we have a function that will eventually call apropos to do the real work – searching for the regexp and displaying the result. The regexp itself is constructed by first parsing the comma separated values (CSV) string into a list of strings, and then generating all possible permutations of this list of strings.
(defun my-apropos-keywords (keywords) "Search for KEYWORDS. This uses `apropos'. All the keywords must match. KEYWORDS can be a comma-separated list." (interactive "sKeywords: (comma-separated) ") (apropos (my-csv-string-to-regexp keywords))) (defun my-csv-string-to-regexp (str) "Translate comma separated values into regexp. A,B,C turns into \\(A.*B.*C\\|A.*C.*B\\|B.*A.*C\\|B.*C.*A\\|C.*A.*B\\|C.*B.*A\\)" (let* ((l (perms (split-string str ",\\s-*")))) (mapconcat (function (lambda (n) (mapconcat 'identity n ".*"))) l "\\|"))) ;; thanks to Christoph Conrad <firstname.lastname@example.org> (require 'cl) (defun perms (l) (if (null l) (list '()) (mapcan #'(lambda( a ) (mapcan #'(lambda( p ) (list (cons a p))) (perms (remove* a l :count 1)))) l)))
Here is my take on “string permutations”.
First we need some helper functions:
(defun rotate-string (s n) (cond ((= (length s) 1) s) ((> (length s) 1) (let ((s2 s) (cnt 0)) (while (< cnt n) (setq s2 (concat (substring s2 1) (substring s2 0 1))) (setq cnt (1+ cnt))) s2)))) (defun list-all-rotated-strings (s) (let ((cnt 0)) (mapcar (lambda (x) (setq cnt (1+ cnt)) (rotate-string s cnt)) s)))
The permutation function:
(defun string-permutations (s) (cond ((null s) nil) ((= (length s) 0) nil) ((= (length s) 1) (list s)) ((= (length s) 2) (list-all-rotated-strings s)) (t (apply 'append (mapcar (lambda (rotn) (mapcar (lambda (perm) (concat (substring rotn 0 1) perm)) (string-permutations (substring rotn 1)))) (list-all-rotated-strings s))))))
When I first tried to do this, I was totally lost. Then I discivered the rotate-trick. Still I could not get it to work. So I googled for it, and found this excellent page:
I converted that to Emacs Lisp (my rotate function intact), and it worked:
(string-permutations "a") => ("a")
(string-permutations "ab") => ("ba" "ab")
(string-permutations "abc") => ("bac" "bca" "cba" "cab" "acb" "abc")
(string-permutations "abcd") => ("bdca" "bdac" "badc" "bacd" "bcad" "bcda" "cadb" "cabd" "cbad" "cbda" "cdba" "cdab" ...)
I probably wouldn’t have gotten the permute function to work unless I had found that page, but at least I was on the right track :) (I knew I needed the rotate function and recursion and about the three special cases).
Recursion is fun, but a bit scary… :)