aerial.utils.math.combinatorics
Various supplementary math functions centering on combinatorics
that are not supplied by clojure.math.combinatorics. Effectively an
extension of that library.
choose-k
(choose-k k coll)
combins
(combins k coll)(combins xfn k coll)
Return the set of all K element _combinations_ (not permutations)
formed from coll. Coll does not need to be a set. In particular,
repeated elements are legal. Combinations are returned as a lazy seq
of vectors, each vector a combination.
In the three argument case, xfn is a transform function applied to
each combination which are passed as vectors - see examples for a
use case. The default is simply identity (used for the 2 argument
signature).
Examples:
(combins 2 "abcdef")
=> ([\a \b] [\a \c] [\a \d] [\a \e] [\a \f] [\b \c]
[\b \d] [\b \e] [\b \f] [\c \d] [\c \e] [\c \f]
[\d \e] [\d \f] [\e \f])
(combins #(apply str %) 2 "AAGGGCGUGG")
=> ("AA" "AG" "AG" "AC" "AG" "AU" "AG" "AG" "AC"
"AG" "AU" "GG" "GC" "GG" "GU" "GC" "GG" "GU"
"CG" "CU" "GU")index-combos
(index-combos n k)
Generate all index combinations - in lexical graphic order and 0
based - of N items taken K at a time. Uses persistent data
structures (vectors), and returns a lazy-seq of vectors.
index-combosv
(index-combosv n k)
Eagerly generate all index combinations in same fashsion as
index-combos (see for details).
WARNING: for large examples where you do not use them all (for
example, taking some subset) this could crash your program. See
index-combos for a LAZY version!
index-perms
(index-perms n)
Lazily generate all permutation indices, without repitition, of
size N. Uses Heap's algorithm.
n!
(n! n)
For positive integer N, compute N factorial.
n-k!
(n-k! n k)
For positive integers N and K, compute (n-k)!
nCk
(nCk n k)
For positive integers N and K, compute N choose K (binomial
coefficient): n!/((n-k)!k!)
next-index-combo
(next-index-combo combo n k)
Generate, the next index combination of N things taken K at a time,
from index combination COMBO. Uses persistent data
structures (vectors). Works by spinning the larger indices faster.
next-index-perm
(next-index-perm n i idx perm)
Generate next permutation from permutation PERM of size N. Uses
Heap's algorithm.
perms
(perms coll)(perms xfn coll)
Permutation item generation without repetition over COLL. xfn is a
transform function applied to each item set generated, and defaults
to simply aggregating them in a vector.
Examples:
(perms "ADN")
=> [[\A \A] [\A \D] [\A \N] [\D \A] [\D \D]
[\D \N] [\N \A] [\N \D] [\N \N]]
(perms str "ADN")
=> ["AA" "AD" "AN" "DA" "DD" "DN" "NA" "ND" "NN"]