Permutations

Function Syntax	(LM:Permutations <l>)
Current Version	1.0

Arguments
Symbol	Type	Description
l	List	List for which to return permutations
Returns
Type	Description
List	List of permutations of elements in the supplied list

Program Description

This subfunction will return a list of all possible permutations of elements in a supplied list.

If a list has n distinct elements (i.e. contains no duplicate items), the number of permutations returned will be n! (factorial).

Otherwise the number of permutations returned will be given by the multinomial coefficient: n!/(m₁!·m₂!·...·m_k!) where m₁,...,m_k are the multiplicities of each element in the list (how many times an element occurs in the list). Hence for the list (1 1 2 3 3), there are 5!/(2!·1!·2!) = 120/4 = 30 permutations.

Select all

;;---------------------=={ Permutations }==-------------------;;
;;                                                            ;;
;;  Returns a list of all permutations of elements in a list  ;;
;;------------------------------------------------------------;;
;;  Author: Lee Mac, Copyright © 2011 - www.lee-mac.com       ;;
;;------------------------------------------------------------;;
;;  Arguments:                                                ;;
;;  l - list to process                                       ;;
;;------------------------------------------------------------;;
;;  Returns: List of all permutations of elements in the list ;;
;;------------------------------------------------------------;;

(defun LM:Permutations ( l )
    (if (cdr l)
        (
            (lambda ( f )
                (f
                    (apply 'append
                        (mapcar
                            (function
                                (lambda ( a )
                                    (mapcar (function (lambda ( b ) (cons a b)))
                                        (LM:Permutations
                                            (   (lambda ( f ) (f a l))
                                                (lambda ( a l )
                                                    (if l
                                                        (if (equal a (car l))
                                                            (cdr l)
                                                            (cons (car l) (f a (cdr l)))
                                                        )
                                                    )
                                                )
                                            )
                                        )
                                    )
                                )
                            )
                            l
                        )
                    )
                )
            )
            (lambda ( l ) (if l (cons (car l) (f (vl-remove (car l) (cdr l))))))
        )
        (list l)
    )
)

Example Function Call

_$ (LM:Permutations '(A B C))
((A B C) (A C B) (B A C) (B C A) (C A B) (C B A))

_$ (LM:Permutations '(1 2 3))
((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))

_$ (LM:Permutations '(1 1 2 1))
((1 1 2 1) (1 1 1 2) (1 2 1 1) (2 1 1 1))

Permutations

Program Description

Example Function Call

Jump To: