newLISP - anagrams generator

puts the fun

back in Lisp

Anagrams

An anagram is a word or phrase made by rearranging the letters in another word or phrase. Making anagrams is a task best solved with a recursive algorithm and a 'natural' for LISP. The following two algorithms take a string and return a list of all possible permutations.

The first of the two algorithms was contributed by Sam Cox and works directly on the string itself. Recursively subsections of the string are exploded, rotated and than joined to form a new string.:

(define (anagrams s)
    (if (<= (length s) 1)
        (list s)
        (flat (map (fn (n) (aux (rotate-string s n)))
                          (sequence 1 (length s))))))

(define (aux rs)
    (map (fn (x) (append (first rs) x)) (anagrams (rest rs))))

(define (rotate-string s n)
    (join (rotate (explode s) n)))

The second algorithm is a bit slower but builds on a generally applicable permutations algorithm. The permutations function generates all possible permuations of offsets into the string, then applies those permuations:

(define (permutations lst)
  (if (= (length lst) 1)
   lst
   (apply append (map (fn (rot) (map (fn (perm) (cons (first rot) perm))
      (permutations (rest rot))))
    (rotations lst)))))

(define (rotations lst)
  (map (fn (x) (rotate lst)) (sequence 1 (length lst))))

(define (anagrams str)
  (map (fn (perm) (select str perm))
     (permutations (sequence 0 (- (length str) 1)))))

Here is a run with the word 'lisp':

(anagrams "lisp") =>

("psil" "psli" "pils" "pisl" "plsi" "plis" "silp" "sipl" "slpi" "slip"
"spil" "spli" "ilps" "ilsp" "ipsl" "ipls" "islp" "ispl" "lpsi" "lpis"
"lsip" "lspi" "lips" "lisp")