Next: util.digest
- Message digester framework, Previous: text.tree
- Lazy text construction, Up: Library modules - Utilities [Contents][Index]
util.combinations
- Combination libraryThis 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?
.
{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.
{util.combinations} For each permutation of a list set, calls proc. Returns an undefined value.
{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.
{util.combinations} Calls proc for each combination of n elements out of set. Returns an undefined value.
{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))
{util.combinations} Calls proc for each subset of 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))
{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: util.digest
- Message digester framework, Previous: text.tree
- Lazy text construction, Up: Library modules - Utilities [Contents][Index]