This site is a static rendering of the Trac instance that was used by R7RS-WG1 for its work on R7RS-small (PDF), which was ratified in 2013. For more information, see Home.

# Combinations­Cowan

2017-06-24 05:15:05
source

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

### Set 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-for-each` proc set
`power-set*-for-each` proc pred set

Calls proc for each subset of set.

`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 src i)`. Therefore, the size of the result list is the same as the size of 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!"
```

### Random operations

These procedures use `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)) ```
`shuffle` vector [ random-source ]

Returns a new vector of the same size as vector, in which elements are randomly permuted.

```(shuffle '#(a b c d e))  ⇒ #(e b d c a)
```