Permutations | ![]() |
(permutate <lst>) ; list of n! permutations
(nth-permutation <i> <lst>) ; i-th permutation only
(permutations <lst> <m>) ; list of permutations into m slots
(permutations-count <n> <m>) ; n!/(n-m)!
(nth-permutations <i> <lst> <m> ) ; i-th permutations (with m slots)
(combinations <lst>) ; list of combinations into m slots
(combinations-count <n> <m>) ; n!/m!(n-m)!
(nth-combinations <i> <lst> <m> ) ; i-th combinations (with m slots)
"How many possibilities do we have to take m things out of n. With combinations we don't put it back, with permutations we do put it back."
Combinations are orderless as a set, permutations follow the order as in a list. The number of combinations are always smaller than the permutations.
PERMUTATE returns all possible permutations of list. The length of the list is always (factorial (length lst))
the size will explode and not be computable on larger lists.
PERMUTATIONS and COMBINATIONS need a second argument <m>, which denotes the number of slots, the size of the resulting lists, and return a list of lists of length <m>. COMBINATIONS return less lists than PERMUTATIONS. COMBINATIONS returns a list containing all unique combinations of <m> elements of <lst>.
Counting functions calculate the number of possible combinations or permutations. FACTORIAL counts the number of PERMUTATE sublists. The count functions are optimized to work with large numbers which might not be computable without special attention.
The NTH- functions return the n'th result list only, without calculating the possibly huge number of all combinations. It also allows easy iterations over combinatorial result lists. The result of an invalid index (negative or greater then the maximal index) is undefined. (nil or cycled). The order is not necessarily the same as with the whole list function.
Limits
With the function COMBINATIONS the argument <lst> must be a list of length less than 30. Exception: If <m> = 2, <lst> may have a length greater than 30. <m> must be a non-negative integer less than 30, and <m> must be less than or equal to (length lst).
Note
The module COMBINATIONS is by default not included in a Stdlib project, nor STDALL.LSP. So it must be added to your project or explicitly required.
(permutate '(0 1 2))
; order is important
=> ((2 1 0) (2 0 1) (1 0 2) (1 2 0) (0 2 1) (0 1 2))
(combinations '(0 1 2 3) 3)
; how to put these 4 elements
=> '((0 1 2)(0 1 3)(0 2 3)(1 2 3))
; into 3 slots as set? orderless.
(permutations '(0 1 2 3) 3)
; plus all permutations in these slots
=> ((2 1 0) (2 0 1) (1 0 2) (1 2 0) (0 2 1) (0 1 2) (3 1 0) (3 0 1) (1 0 3) (1 3 0) (0 3 1) (0 1 3) (3 2 0) (3 0 2) (2 0 3) (2 3 0) (0 3 2) (0 2 3) (3 2 1) (3 1 2) (2 1 3) (2 3 1) (1 3 2) (1 2 3)) (permutations '(a b c) 2) => ((a b)(b a)(a c)(c a)(c b)(b c)) (factorial 3) => 6 (factorial 4) => 12 (combinations-count 4 3) => 4 (permutations-count 4 3) => 12 (factorial 17) => 355687428096000.0 (nth-permutations 0 '(a b c) 2) => (C B) (nth-permutations 1 '(a b c) 2) => (B C) (nth-permutations 2 '(a b c) 2) => (C A) ... (nth-permutation 0 '(a b c)) => (C B A) (nth-permutation 1 '(a b c)) => (B C A) (nth-permutation 2 '(a b c)) => (C A B) ... (nth-combinations 0 '(a b c) 2) => (B C) (nth-combinations 1 '(a b c) 2) => (A C) (nth-combinations 2 '(a b c) 2) => (A B) (nth-combinations 3 '(a b c) 2) => nil
lst: Any proper list.
n, m: Any positive integer number, hopefully not too large.
The list functions return a list or a list of lists.
The count functions return an integer or real number.
None.
(std-require 'COMBINATIONS)
Defined in COMBINATIONS
The NTH- functions came with version 1.6