Combinations­Cowan

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)