rlm@10: ;;; combinatorics.clj: efficient, functional algorithms for generating lazy rlm@10: ;;; sequences for common combinatorial functions. rlm@10: rlm@10: ;; by Mark Engelberg (mark.engelberg@gmail.com) rlm@10: ;; January 27, 2009 rlm@10: rlm@10: (comment rlm@10: " rlm@10: (combinations items n) - A lazy sequence of all the unique rlm@10: ways of taking n different elements from items. rlm@10: Example: (combinations [1 2 3] 2) -> ((1 2) (1 3) (2 3)) rlm@10: rlm@10: (subsets items) - A lazy sequence of all the subsets of rlm@10: items (but generalized to all sequences, not just sets). rlm@10: Example: (subsets [1 2 3]) -> (() (1) (2) (3) (1 2) (1 3) (2 3) (1 2 3)) rlm@10: rlm@10: (cartesian-product & seqs) - Takes any number of sequences rlm@10: as arguments, and returns a lazy sequence of all the ways rlm@10: to take one item from each seq. rlm@10: Example: (cartesian-product [1 2] [3 4]) -> ((1 3) (1 4) (2 3) (2 4)) rlm@10: (cartesian-product seq1 seq2 seq3 ...) behaves like but is rlm@10: faster than a nested for loop, such as: rlm@10: (for [i1 seq1 i2 seq2 i3 seq3 ...] (list i1 i2 i3 ...)) rlm@10: rlm@10: (selections items n) - A lazy sequence of all the ways to rlm@10: take n (possibly the same) items from the sequence of items. rlm@10: Example: (selections [1 2] 3) -> ((1 1 1) (1 1 2) (1 2 1) (1 2 2) (2 1 1) (2 1 2) (2 2 1) (2 2 2)) rlm@10: rlm@10: (permutations items) - A lazy sequence of all the permutations rlm@10: of items. rlm@10: Example: (permutations [1 2 3]) -> ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1)) rlm@10: rlm@10: (lex-permutations items) - A lazy sequence of all distinct rlm@10: permutations in lexicographic order rlm@10: (this function returns the permutations as rlm@10: vectors). Only works on sequences of comparable rlm@10: items. (Note that the result will be quite different from rlm@10: permutations when the sequence contains duplicate items.) rlm@10: Example: (lex-permutations [1 1 2]) -> ([1 1 2] [1 2 1] [2 1 1]) rlm@10: rlm@10: About permutations vs. lex-permutations: rlm@10: lex-permutations is faster than permutations, but only works rlm@10: on sequences of numbers. They operate differently rlm@10: on sequences with duplicate items (lex-permutations will only rlm@10: give you back distinct permutations). lex-permutations always rlm@10: returns the permutations sorted lexicographically whereas rlm@10: permutations will be in an order where the input sequence rlm@10: comes first. In general, I recommend using the regular rlm@10: permutations function unless you have a specific rlm@10: need for lex-permutations. rlm@10: rlm@10: About this code: rlm@10: These combinatorial functions can be written in an elegant way using recursion. However, when dealing with combinations and permutations, you're usually generating large numbers of things, and speed counts. My objective was to write the fastest possible code I could, restricting myself to Clojure's functional, persistent data structures (rather than using Java's arrays) so that this code could be safely leveraged within Clojure's transactional concurrency system. rlm@10: rlm@10: I also restricted myself to algorithms that return results in a standard order. For example, there are faster ways to generate cartesian-product, but I don't know of a faster way to generate the results in the standard nested-for-loop order. rlm@10: rlm@10: Most of these algorithms are derived from algorithms found in Knuth's wonderful Art of Computer Programming books (specifically, the volume 4 fascicles), which present fast, iterative solutions to these common combinatorial problems. Unfortunately, these iterative versions are somewhat inscrutable. If you want to better understand these algorithms, the Knuth books are the place to start. rlm@10: rlm@10: On my own computer, I use versions of all these algorithms that return sequences built with an uncached variation of lazy-seq. Not only does this boost performance, but it's easier to use these rather large sequences more safely (from a memory consumption standpoint). If some form of uncached sequences makes it into Clojure, I will update this accordingly. rlm@10: " rlm@10: ) rlm@10: rlm@10: rlm@10: (ns rlm@10: ^{:author "Mark Engelberg", rlm@10: :doc "Efficient, functional algorithms for generating lazy rlm@10: sequences for common combinatorial functions. (See the source code rlm@10: for a longer description.)"} rlm@10: clojure.contrib.combinatorics) rlm@10: rlm@10: (defn- index-combinations rlm@10: [n cnt] rlm@10: (lazy-seq rlm@10: (let [c (vec (cons nil (for [j (range 1 (inc n))] (+ j cnt (- (inc n)))))), rlm@10: iter-comb rlm@10: (fn iter-comb [c j] rlm@10: (if (> j n) nil rlm@10: (let [c (assoc c j (dec (c j)))] rlm@10: (if (< (c j) j) [c (inc j)] rlm@10: (loop [c c, j j] rlm@10: (if (= j 1) [c j] rlm@10: (recur (assoc c (dec j) (dec (c j))) (dec j)))))))), rlm@10: step rlm@10: (fn step [c j] rlm@10: (cons (rseq (subvec c 1 (inc n))) rlm@10: (lazy-seq (let [next-step (iter-comb c j)] rlm@10: (when next-step (step (next-step 0) (next-step 1)))))))] rlm@10: (step c 1)))) rlm@10: rlm@10: (defn combinations rlm@10: "All the unique ways of taking n different elements from items" rlm@10: [items n] rlm@10: (let [v-items (vec (reverse items))] rlm@10: (if (zero? n) (list ()) rlm@10: (let [cnt (count items)] rlm@10: (cond (> n cnt) nil rlm@10: (= n cnt) (list (seq items)) rlm@10: :else rlm@10: (map #(map v-items %) (index-combinations n cnt))))))) rlm@10: rlm@10: (defn subsets rlm@10: "All the subsets of items" rlm@10: [items] rlm@10: (mapcat (fn [n] (combinations items n)) rlm@10: (range (inc (count items))))) rlm@10: rlm@10: (defn cartesian-product rlm@10: "All the ways to take one item from each sequence" rlm@10: [& seqs] rlm@10: (let [v-original-seqs (vec seqs) rlm@10: step rlm@10: (fn step [v-seqs] rlm@10: (let [increment rlm@10: (fn [v-seqs] rlm@10: (loop [i (dec (count v-seqs)), v-seqs v-seqs] rlm@10: (if (= i -1) nil rlm@10: (if-let [rst (next (v-seqs i))] rlm@10: (assoc v-seqs i rst) rlm@10: (recur (dec i) (assoc v-seqs i (v-original-seqs i)))))))] rlm@10: (when v-seqs rlm@10: (cons (map first v-seqs) rlm@10: (lazy-seq (step (increment v-seqs)))))))] rlm@10: (when (every? first seqs) rlm@10: (lazy-seq (step v-original-seqs))))) rlm@10: rlm@10: rlm@10: (defn selections rlm@10: "All the ways of taking n (possibly the same) elements from the sequence of items" rlm@10: [items n] rlm@10: (apply cartesian-product (take n (repeat items)))) rlm@10: rlm@10: rlm@10: (defn- iter-perm [v] rlm@10: (let [len (count v), rlm@10: j (loop [i (- len 2)] rlm@10: (cond (= i -1) nil rlm@10: (< (v i) (v (inc i))) i rlm@10: :else (recur (dec i))))] rlm@10: (when j rlm@10: (let [vj (v j), rlm@10: l (loop [i (dec len)] rlm@10: (if (< vj (v i)) i (recur (dec i))))] rlm@10: (loop [v (assoc v j (v l) l vj), k (inc j), l (dec len)] rlm@10: (if (< k l) rlm@10: (recur (assoc v k (v l) l (v k)) (inc k) (dec l)) rlm@10: v)))))) rlm@10: rlm@10: (defn- vec-lex-permutations [v] rlm@10: (when v (cons v (lazy-seq (vec-lex-permutations (iter-perm v)))))) rlm@10: rlm@10: (defn lex-permutations rlm@10: "Fast lexicographic permutation generator for a sequence of numbers" rlm@10: [c] rlm@10: (lazy-seq rlm@10: (let [vec-sorted (vec (sort c))] rlm@10: (if (zero? (count vec-sorted)) rlm@10: (list []) rlm@10: (vec-lex-permutations vec-sorted))))) rlm@10: rlm@10: (defn permutations rlm@10: "All the permutations of items, lexicographic by index" rlm@10: [items] rlm@10: (let [v (vec items)] rlm@10: (map #(map v %) (lex-permutations (range (count v))))))