For Gauche 0.9.10

Next: , Previous: , Up: Library modules - Utilities   [Contents][Index]

### 12.69 `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

{util.combinations} 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

{util.combinations} For each permutation of a list set, calls proc. Returns an undefined value.

Function: combinations set n
Function: combinations* set n :optional eq

{util.combinations} 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

{util.combinations} 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

{util.combinations} 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

{util.combinations} Calls proc for each subset of set.

Function: power-set-binary set

{util.combinations} 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

{util.combinations} 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))
```

Next: , Previous: , Up: Library modules - Utilities   [Contents][Index]