This SRFI implements several useful procedures of combinations, permutations and related operations.

Sets in the following procedures are in
the sense of SRFI 1, that is, lists.
Some of these procedures have two variants: a procedure without
star (e.g. `permutations`

) treats all elements in the given
set distinct, while a procedure with star (e.g. `permutations*`

)
considers duplication. The procedures with star take a `pred`
argument that is used to test equality.

`permutations`

*set*`permutations*`

*pred set*Returns a list of all permutations of a list

`set`.(permutations '(a b c)) ⇒ ((a b c) (a c b) (b a c) (b c a) (c a b) (c b a)) (permutations '(a a b)) ⇒ ((a a b) (a b a) (a a b) (a b a) (b a a) (b a a)) (permutations* '(a a b)) ⇒ ((a a b) (a b a) (b a a))

The number of possible permutations explodes if

`set`has more than several elements. Use with care. If you want to process each permutation at a time, consider`permutations-for-each`

below.

`permutations-for-each`

*proc set*`permutations*-for-each`

*proc pred set*For each permutation of a list

`set`, calls`proc`. Returns an undefined value.

`combinations`

*set n*`combinations*`

*pred set n*Returns a list of all possible combinations of

`n`elements out of a list`set`.(combinations '(a b c) 2) ⇒ ((a b) (a c) (b c)) (combinations '(a a b) 2) ⇒ ((a a) (a b) (a b)) (combinations* '(a a b) 2) ⇒ ((a a) (a b))

Watch out for the explosion of combinations when

`set`is large.

`combinations-for-each`

*proc set n*`combinations*-for-each`

*proc pred set n*Calls

`proc`for each combination of`n`elements out of`set`. Returns an undefined value.

`power-set`

*set*`power-set*`

*pred set*Returns power set (all subsets) of a list

`set`.(power-set '(a b c)) ⇒ (() (a) (b) (c) (a b) (a c) (b c) (a b c)) (power-set* '(a a b) ⇒ (() (a) (b) (a a) (a b) (a a b))

`power-set-binary`

*set*Returns power set of

`set`, like`power-set`

, but in different order.`Power-set-binary`

traverses subset space in depth-first order, while`power-set`

in breadth-first order.(power-set-binary '(a b c)) ⇒ (() (c) (b) (b c) (a) (a c) (a b) (a b c))

`cartesian-product`

*list-of-sets*`cartesian-product-right`

*list-of-sets*Returns a cartesian product of sets in

`list-of-sets`.`Cartesian-product`

construct the result in left fixed order (the rightmost element varies first), while`cartesian-product-right`

in right fixed order (the leftmost element varies first).(cartesian-product '((a b c) (0 1))) ⇒ ((a 0) (a 1) (b 0) (b 1) (c 0) (c 1)) (cartesian-product-right '((a b c) (0 1))) ⇒ ((a 0) (b 0) (c 0) (a 1) (b 1) (c 1))

`group-list`

*list [ key [ test ] ]*Groups consecutive elements in a list

`list`which have the common key value. A key value of an element is obtained by applying the procedure`key`to the element; the default procedure is`identity`

. For each element in`list`,`key`is applied exactly once. The equal-ness of keys are compared by`test`procedure, whose default is`eqv?`

.(group-list '(1 1 1 2 3 4 4 2 2 3 1 1 3)) ⇒ ((1 1 1) (2) (3) (4 4) (2 2) (3) (1 1) (3)) (group-list '(1 1 1 2 3 4 4 2 2 3 1 1 3) :key (cut modulo <> 2))) ⇒ ((1 1 1) (2) (3) (4 4 2 2) (3 1 1 3)) (group-list '#("a" "a" "b" "b" "c" "d" "d") :test string=?) ⇒ (("a" "a") ("b" "b") ("c") ("d" "d")) (group-list "aabbcdd" :test char=?) ⇒ ((#\a #\a) (#\b #\b) (#\c) (#\d #\d))

`permute`

*vector permuter [ fallback ]*Returns a newly created vector, in which the elements are permuted from

`src`according to`permuter`.`Permuter`is a list of exact integers. When the`k`-th element of`permuter`is`i`, the`k`-th element of the result is`(ref`

. Therefore, the size of the result list is the same as the size of`src``i`)`permuter`.`Permuter`can be any kind of list, unrelated to the type of`src`.The same index

`i`can appear more than once in`permuter`.(permute '#(a b c d) '(3 2 0 1)) ⇒ #(d c a b) (permute '#(a b c d) '(0 2)) ⇒ #(a c) (permute '#(a b c d) '(0 0 1 1 2 2)) ⇒ #(a a b b c c)

If an integer in

`permuter`is out of the valid range for an index of`vector`, then`fallback`is returned.(permute '#(a b c) '(3 2 1 0) 'foo) ⇒ #(foo c b a) (permute "!,HWdelor" #(2 5 6 6 7 1 -1 3 7 8 6 4 0) #\space) ⇒ "Hello, World!"

`default-random-source`

from
SRFI 27.
`make-permutation-generator`

*vector*Returns a generator that yields random permutations of

`vector`.(generator->list (make-permutation-generator '(1 2 3)) 3) ⇒ ((1 2 3) (2 3 1) (3 2 1)) (generator->list (make-permutation-generator "abc") 3) ⇒ ("cba" "cba" "cab")

`make-combination-generator`

*size vector*Returns a generator that yields vectors of

`size`elements randomly picked from`vector`.(generator->list (make-combination-generatorh 2 #(a b c)) 5) ⇒ (#(a c) #(a b) #(a c) #(b a) #(a c)) (generator->list (make-combination-generator 2 '#(a b c)) 5) ⇒ (#(a c) #(b c) #(c b) #(b a) #(b c))