A Clojure and ClojureScript library of combinatorics functions based on the building of a combination tree.
Link to the latest codox API docs.
Latest release: 0.1.0-SNAPSHOT
Leiningen dependency information:
[combi-tree/combi-tree "0.1.0-SNAPSHOT"]This library provides functions to:
- generate a combination tree given an original collection,
- generate combinations given a previously generated combination tree,
- generate combinations given an original collection.
The functions that generate combinations are really there for convenience and easier testing. When no combination tree is required, it is best to use the more efficient match.combinatorics library.
A combination tree of depth n is a tree which nodes and leafs are items of an
original collection so that each path to a leaf provides a possible combination
of n items of the original collection, while still preserving their original
order.
Combination trees are particularly useful when one needs to parse an input and
check if it's a non-ambiguous combination of items from a reference collection.
combinations-tree and combinations do not check for duplicates while
distinct-combinations-tree and distinct-combinations do. The value of this
library really lies in the latter two functions that handle duplicates because
they enable to quickly detect duplicates (ambiguous input).
A combination tree is made up of nested sequences, whereby each sequence head is a node (an item from the original collection) and the tail is made up of the children of that node. The top level however is a sequence of root children with no root node at the head.
Since the tree structure is made of sequences there is a risk of ambiguity if
the original collection also contains sequences (how to distinguish a sequence
that is part of the tree structure from a sequence that comes from the original
collection?). To avoid this situation, the sequences that are part of the
generated tree structure are tagged with a meta-data element
(see with-tree-meta function).
Consequently it's best to always use trees generated by this library.
Most functions return lazy or partially lazy sequences.
(ns example.core
(:require [combi-tree.combi-tree :as combit]))
(combit/combinations-tree [1 2 3 4] 2)
;;=> ((1 2 3 4) (2 3 4) (3 4))
(combit/combinations-tree [1 2 3 4] 3)
;;=> ((1 (2 3 4) (3 4)) (2 (3 4)))
(combit/combinations-tree [1 1 3 4] 3)
;;=> ((1 (1 3 4) (3 4)) (1 (3 4)))
(combit/distinct-combinations-tree [1 1 3 4] 3)
;;=> ((1 (1 3 4) (3 (4 :combi-tree.combi-tree/dups))))
(combit/distinct-combinations [1 1 3 4] 3)
;;=> ((1 1 3) (1 1 4) (1 3 4))
(combit/combinations [1 1 3 4] 3)
;;=> ((1 1 3) (1 1 4) (1 3 4) (1 3 4))Copyright © 2015 François Rey
Distributed under the Eclipse Public License either version 1.0 or (at your option) any later version.