9 replies to this topic

[John]

Code to generate the permutations of a given list in Common Lisp.
Code:

(defun p (l)
  (if (null l) '(())
  (mapcan #'(lambda (x)
    (mapcar #'(lambda (y) (cons x y))
      (p (remove x l :count 1)))) l)))

Usage/Output:

* (load "permute.lsp")  

; Loading #p"/home/john/permute.lsp".
T
* (p (list 'a 'b 'c 'd 'e))

((A B C D E) (A B C E D) (A B D C E) (A B D E C) (A B E C D) (A B E D C)
 (A C B D E) (A C B E D) (A C D B E) (A C D E B) (A C E B D) (A C E D B)
 (A D B C E) (A D B E C) (A D C B E) (A D C E B) (A D E B C) (A D E C B)
 (A E B C D) (A E B D C) (A E C B D) (A E C D B) (A E D B C) (A E D C B)
 (B A C D E) (B A C E D) (B A D C E) (B A D E C) (B A E C D) (B A E D C)
 (B C A D E) (B C A E D) (B C D A E) (B C D E A) (B C E A D) (B C E D A)
 (B D A C E) (B D A E C) (B D C A E) (B D C E A) (B D E A C) (B D E C A)
 (B E A C D) (B E A D C) (B E C A D) (B E C D A) (B E D A C) (B E D C A)
 (C A B D E) (C A B E D) (C A D B E) (C A D E B) (C A E B D) (C A E D B)
 (C B A D E) (C B A E D) (C B D A E) (C B D E A) (C B E A D) (C B E D A)
 (C D A B E) (C D A E B) (C D B A E) (C D B E A) (C D E A B) (C D E B A)
 (C E A B D) (C E A D B) (C E B A D) (C E B D A) (C E D A B) (C E D B A)
 (D A B C E) (D A B E C) (D A C B E) (D A C E B) (D A E B C) (D A E C B)
 (D B A C E) (D B A E C) (D B C A E) (D B C E A) (D B E A C) (D B E C A)
 (D C A B E) (D C A E B) (D C B A E) (D C B E A) (D C E A B) (D C E B A)
 (D E A B C) (D E A C B) (D E B A C) (D E B C A) (D E C A B) (D E C B A)
 (E A B C D) (E A B D C) (E A C B D) (E A C D B) (E A D B C) (E A D C B)
 (E B A C D) (E B A D C) (E B C A D) (E B C D A) (E B D A C) (E B D C A)
 (E C A B D) (E C A D B) (E C B A D) (E C B D A) (E C D A B) (E C D B A)
 (E D A B C) (E D A C B) (E D B A C) (E D B C A) (E D C A B) (E D C B A))

[BlaineSch]

I am a bit confused - mind explaining this one to me?

[John]

Can you be more precise as to what your confused about?

[BlaineSch]

What language this is? I tried looking up most of the words in your post and still couldnt piece together what this code is or does...

[John]

The language is `lisp' and the code generates permutations.

[BlaineSch]

So from what I can tell the program loads "a, b, c, d, e" and then makes a list of every combination of those letters starting from "a, b, c, d, e" to "e, d, c, b, a" using a simple 5 line code? This could possibly be used for some type of spellcheck or word guessing program, even possibly an encryption/decryption program?

[John]

Yes.

(p (list 'a 'b 'c 'd 'e)

Simply calls the function "p" and passes it a list of "a, b, c, d, e"

Those 5 files of code generate a list of all possible combinations of those letters.

[BlaineSch]

Think you could explain your code line by line - I am not familiar with the 'lisp' language but it seems like it could come in handy for a lot of things.

(defun p (l) //defines the function "p" with the list "l"
  (if (null l) '(()) //if the list is null then exit?
  (mapcan #'(lambda (x) //now I just get lost...
    (mapcar #'(lambda (y) (cons x y))
      (p (remove x l :count 1)))) l)))

[John]

The `lambdas' are anonymous functions which are arguments to the mapcan and mapcar functions. (http://forum.codecal...xpressions.html)

From the documentation: (Simplified Common Lisp reference)

CONS function make new cons object. The cons cell contains exactly two values. The first is named car, the second is named cdr. These cells are used to create one-way linked lists. See also CAR, CDR and LIST.

MAPCAN applies function FN to elements of lists with same index. Each application result is concatenated into resulting list. See MAPCAR.

MAPCAR applies function FN to elements of lists with same index. Each application result is put into resulting list. Length of resulting list is the length of the shortest list argument.

LISP is a neat language, but the syntax is garbage.

[silvain]

Fascinating to get the list of all the permutations of a list in such a short lisp code !!
This illustrates the power of LISP.
The code uses

• the recursive potential of LISP (p is used in the definition of the function p)
  
• the lambda constructs which can define a function on the fly (without giving it any name) to apply it to arguments at the same time
  
• the mapcar and mapcan functions which can distribute the action of a function to a list of objects

This procedure can be roughly explained in common language :

• Take out each element x of the list in turn, and you obtain a shorter sublist l, and for each x ...
  
• Put x in front of all the permutations [here you use the recursivity] of the shorter sublist l to get all the permutations of the initial list starting with x
  
• When the recursive procedure gets into a empty list, it is finished.
  
• You have then obtained the list of all the permutations of the intial list