Someone in #lisp asked about permutations the other day. I hadn’t come across them before so after looking up what they where I decided it sounded like a good programming exercise to try and find all the permutations for a given string.
Anyway, it took me a little while to figure out how to do it but once I did it wasn’t so hard, here’s the code:
(defuntranspose(stringposition)"Return string with the characters at position transposed"(let((before(when(>position0)(subseqstring0position)))(after(when(<(+1position)(lengthstring))(subseqstring(+2position)))))(concatenate'stringbefore(subseqstring(+position1)(+position2))(subseqstringposition(+position1))after)))(defunpermutations-helper(permutationsposition)"Does the hard work for the permutations function."(cond((notpermutations)nil)((eql(length(carpermutations))(+position1))permutations)(t(permutations-helper(appendpermutations(mapcar(lambda(x)(transposexposition))permutations))(+1position)))))(defunpermutations(string)"Take a string and return a list of it's permutations"(remove-duplicates(permutations-helper(liststring)0):test#'equal))(permutations"population")
Any feedback would be great, feel free to use the code.
Cheers, Dave.
Edit: Before I re-wrote my blog there was a great comment from Kelsar that corrected the above code. I’ve included it below so anyone reading this has a working example to peek at and to help demonstrate what’s wrong with the above example.
There is something wrong in your program; for example: (member "trebor" (permutations "robert")) -> NIL
You probably need something like "rotation" of string. This is my version (on lists, not strings, but this is the same):
Edit 2: This old post caught my eye, the year is now 2015, and it’s been quite a while since I’ve done any Lisp! Here’s a quick version of Kelsar’s algorithm rewritten in Clojure: