Mercurial > lasercutter

comparison src/clojure/contrib/combinatorics.clj @ 10:ef7dbbd6452c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
added clojure source goodness
author Robert McIntyre <rlm@mit.edu>
date Sat, 21 Aug 2010 06:25:44 -0400
parents
children
comparison
equal deleted inserted replaced
9:35cf337adfcf 10:ef7dbbd6452c
1 ;;; combinatorics.clj: efficient, functional algorithms for generating lazy
2 ;;; sequences for common combinatorial functions.
3
4 ;; by Mark Engelberg (mark.engelberg@gmail.com)
5 ;; January 27, 2009
6
7 (comment
8 "
9 (combinations items n) - A lazy sequence of all the unique
10 ways of taking n different elements from items.
11 Example: (combinations [1 2 3] 2) -> ((1 2) (1 3) (2 3))
12
13 (subsets items) - A lazy sequence of all the subsets of
14 items (but generalized to all sequences, not just sets).
15 Example: (subsets [1 2 3]) -> (() (1) (2) (3) (1 2) (1 3) (2 3) (1 2 3))
16
17 (cartesian-product & seqs) - Takes any number of sequences
18 as arguments, and returns a lazy sequence of all the ways
19 to take one item from each seq.
20 Example: (cartesian-product [1 2] [3 4]) -> ((1 3) (1 4) (2 3) (2 4))
21 (cartesian-product seq1 seq2 seq3 ...) behaves like but is
22 faster than a nested for loop, such as:
23 (for [i1 seq1 i2 seq2 i3 seq3 ...] (list i1 i2 i3 ...))
24
25 (selections items n) - A lazy sequence of all the ways to
26 take n (possibly the same) items from the sequence of items.
27 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))
28
29 (permutations items) - A lazy sequence of all the permutations
30 of items.
31 Example: (permutations [1 2 3]) -> ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))
32
33 (lex-permutations items) - A lazy sequence of all distinct
34 permutations in lexicographic order
35 (this function returns the permutations as
36 vectors). Only works on sequences of comparable
37 items. (Note that the result will be quite different from
38 permutations when the sequence contains duplicate items.)
39 Example: (lex-permutations [1 1 2]) -> ([1 1 2] [1 2 1] [2 1 1])
40
41 About permutations vs. lex-permutations:
42 lex-permutations is faster than permutations, but only works
43 on sequences of numbers. They operate differently
44 on sequences with duplicate items (lex-permutations will only
45 give you back distinct permutations). lex-permutations always
46 returns the permutations sorted lexicographically whereas
47 permutations will be in an order where the input sequence
48 comes first. In general, I recommend using the regular
49 permutations function unless you have a specific
50 need for lex-permutations.
51
52 About this code:
53 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.
54
55 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.
56
57 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.
58
59 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.
60 "
61 )
62
63
64 (ns
65 ^{:author "Mark Engelberg",
66 :doc "Efficient, functional algorithms for generating lazy
67 sequences for common combinatorial functions. (See the source code
68 for a longer description.)"}
69 clojure.contrib.combinatorics)
70
71 (defn- index-combinations
72 [n cnt]
73 (lazy-seq
74 (let [c (vec (cons nil (for [j (range 1 (inc n))] (+ j cnt (- (inc n)))))),
75 iter-comb
76 (fn iter-comb [c j]
77 (if (> j n) nil
78 (let [c (assoc c j (dec (c j)))]
79 (if (< (c j) j) [c (inc j)]
80 (loop [c c, j j]
81 (if (= j 1) [c j]
82 (recur (assoc c (dec j) (dec (c j))) (dec j)))))))),
83 step
84 (fn step [c j]
85 (cons (rseq (subvec c 1 (inc n)))
86 (lazy-seq (let [next-step (iter-comb c j)]
87 (when next-step (step (next-step 0) (next-step 1)))))))]
88 (step c 1))))
89
90 (defn combinations
91 "All the unique ways of taking n different elements from items"
92 [items n]
93 (let [v-items (vec (reverse items))]
94 (if (zero? n) (list ())
95 (let [cnt (count items)]
96 (cond (> n cnt) nil
97 (= n cnt) (list (seq items))
98 :else
99 (map #(map v-items %) (index-combinations n cnt)))))))
100
101 (defn subsets
102 "All the subsets of items"
103 [items]
104 (mapcat (fn [n] (combinations items n))
105 (range (inc (count items)))))
106
107 (defn cartesian-product
108 "All the ways to take one item from each sequence"
109 [& seqs]
110 (let [v-original-seqs (vec seqs)
111 step
112 (fn step [v-seqs]
113 (let [increment
114 (fn [v-seqs]
115 (loop [i (dec (count v-seqs)), v-seqs v-seqs]
116 (if (= i -1) nil
117 (if-let [rst (next (v-seqs i))]
118 (assoc v-seqs i rst)
119 (recur (dec i) (assoc v-seqs i (v-original-seqs i)))))))]
120 (when v-seqs
121 (cons (map first v-seqs)
122 (lazy-seq (step (increment v-seqs)))))))]
123 (when (every? first seqs)
124 (lazy-seq (step v-original-seqs)))))
125
126
127 (defn selections
128 "All the ways of taking n (possibly the same) elements from the sequence of items"
129 [items n]
130 (apply cartesian-product (take n (repeat items))))
131
132
133 (defn- iter-perm [v]
134 (let [len (count v),
135 j (loop [i (- len 2)]
136 (cond (= i -1) nil
137 (< (v i) (v (inc i))) i
138 :else (recur (dec i))))]
139 (when j
140 (let [vj (v j),
141 l (loop [i (dec len)]
142 (if (< vj (v i)) i (recur (dec i))))]
143 (loop [v (assoc v j (v l) l vj), k (inc j), l (dec len)]
144 (if (< k l)
145 (recur (assoc v k (v l) l (v k)) (inc k) (dec l))
146 v))))))
147
148 (defn- vec-lex-permutations [v]
149 (when v (cons v (lazy-seq (vec-lex-permutations (iter-perm v))))))
150
151 (defn lex-permutations
152 "Fast lexicographic permutation generator for a sequence of numbers"
153 [c]
154 (lazy-seq
155 (let [vec-sorted (vec (sort c))]
156 (if (zero? (count vec-sorted))
157 (list [])
158 (vec-lex-permutations vec-sorted)))))
159
160 (defn permutations
161 "All the permutations of items, lexicographic by index"
162 [items]
163 (let [v (vec items)]
164 (map #(map v %) (lex-permutations (range (count v))))))