Next: Message digester framework, Previous: Lazy text construction, Up: Library modules - Utilities [Contents][Index]

`util.combinations`

- Combination library- Module:
**util.combinations** -
This module implements several useful procedures of combinations, permutations and related operations.

Most procedures in the module 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 optional`eq`argument that is used to test equality, which defaults to`eqv?`

.

- Function:
**permutations***set* - Function:
**permutations****set :optional eq* 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.

- Function:
**permutations-for-each***proc set* - Function:
**permutations*-for-each***proc set :optional eq* For each permutation of a list

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

- Function:
**combinations***set n* - Function:
**combinations****set n :optional eq* 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 the explosion of combinations when

`set`is large.

- Function:
**combinations-for-each***proc set n* - Function:
**combinations*-for-each***proc set n :optional eq* Calls

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

- Function:
**power-set***set* - Function:
**power-set****set :optional eq* 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))

- Function:
**power-set-for-each***proc set* - Function:
**power-set*-for-each***proc set :optional eq* Calls

`proc`for each subset of`set`.

- Function:
**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))

- Function:
**cartesian-product***list-of-sets* - Function:
**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))