CombinationsCowan

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

Many 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 optional eq argument that is used to test equality, which defaults to eqv?.

permutations set

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.

permutations-for-each proc set
permutations*-for-each proc set :optional eq: For each permutation of a list set, calls proc. Returns an undefined value.

combinations set n

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.

combinations-for-each proc set n
combinations*-for-each proc set n :optional eq: Calls proc for each combination of n elements out of set. Returns an undefined value.

power-set set

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))

power-set-for-each proc set
power-set*-for-each proc set :optional eq: 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))

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))

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))

This method is similar to Haskell’s group. If you want to group elements that are not adjacent, use group-collection (see Selection and searching in collection).

permute src permuter [ fallback ]

Returns a newly created list of the same type as src, 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.

It is allowed that 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 as the index of src, then an error is signaled unless fallback is given. If fallback is given, what value is used depends on the result of (ref src i fallback)—which usually returns fallback for the out-of-range index i.

(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!"

shuffle src [ random-source ]

Returns a new list of the same type and size as src, in which elements are randomly permuted.

(shuffle '(a b c d e))  ⇒ (e b d c a)
(shuffle "abcde")       ⇒ "bacde"

This generic function uses SRFI 27. By default it uses default-random-source, but you can pass an alternative random source by the optional argument.

Combinations­Cowan

CombinationsCowan