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!/(m1!·m2!·...·mk!) where m1,...,mk 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))