Debian Codegraph @

lib/util/combinations.scm

raw
1 ;;;
2 ;;; combinations.scm - combinations and that sort of stuff.
3 ;;;
4 ;;; Copyright(C) 2003 by Alex Shinn ([email protected])
5 ;;; Copyright (c) 2003-2024 Shiro Kawai <[email protected]>
6 ;;;
7 ;;; Permission to use, copy, modify, distribute this software and
8 ;;; accompanying documentation for any purpose is hereby granted,
9 ;;; provided that existing copyright notices are retained in all
10 ;;; copies and that this notice is included verbatim in all
11 ;;; distributions.
12 ;;; This software is provided as is, without express or implied
13 ;;; warranty. In no circumstances the author(s) shall be liable
14 ;;; for any damages arising out of the use of this software.
15 ;;;
16
17 ;; Initially written by Alex Shinn.
18 ;; Modifided by Shiro Kawai
19
20 (define-module util.combinations
21 (use scheme.list)
22 (use util.match)
23 (use gauche.sequence)
24 (export permutations permutations*
25 permutations-for-each permutations*-for-each
26 combinations combinations*
27 combinations-for-each combinations*-for-each
28 power-set-binary power-set power-set-for-each
29 power-set* power-set*-for-each
30 cartesian-product cartesian-product-for-each
31 cartesian-product-right cartesian-product-right-for-each)
32 )
33 (select-module util.combinations)
34
35 ;;----------------------------------------------------------------
36 ;; permuations
37 ;;
38
39 ;; return a list of k-th element is removed
40 (define (but-kth lis k)
41 (case k
42 [(0) (cdr lis)]
43 [(1) (cons (car lis) (cddr lis))]
44 [(2) (list* (car lis) (cadr lis) (cdddr lis))]
45 [(3) (list* (car lis) (cadr lis) (caddr lis) (cddddr lis))]
46 [else (receive (head tail) (split-at lis k)
47 (append! head (cdr tail)))]))
48
49 ;; permute set. all elements are considered distinct.
50 ;; the shortcut for 3 elements or less speeds up a bit.
51 (define (permutations set)
52 (match set
53 [() (list '())]
54 [(a) (list set)]
55 [(a b) `(,set (,b ,a))]
56 [(a b c)
57 `(,set (,a ,c ,b) (,b ,a ,c) (,b ,c ,a) (,c ,a ,b) (,c ,b ,a))]
58 [else
59 (reverse!
60 (fold-with-index
61 (^[ind elt acc]
62 (fold (^[subperm acc] (acons elt subperm acc))
63 acc
64 (permutations (but-kth set ind))))
65 '()
66 set))]))
67
68 ;; permute set, considering equal elements, a.k.a multiset permutations
69 (define (permutations* set :optional (eq eqv?))
70 (define (rec set)
71 (match set
72 [() (list '())]
73 [(a) (list set)]
74 [(a b) (if (eq a b) (list set) `(,set (,b ,a)))]
75 [else
76 (let loop ((i 0)
77 (seen '())
78 (p set)
79 (r '()))
80 (cond [(null? p) (reverse! r)]
81 [(member (car p) seen eq) (loop (+ i 1) seen (cdr p) r)]
82 [else
83 (loop (+ i 1)
84 (cons (car p) seen)
85 (cdr p)
86 (fold (^[subperm r] (acons (car p) subperm r))
87 r
88 (rec (but-kth set i))))]))]))
89 (rec set))
90
91 ;; permutations without generating entire list.
92 ;; We use shortcut for (<= length 4) case, which boosts performace.
93 (define-inline (p/each3 proc x1 x2 x3)
94 (proc `(,x1 ,x2 ,x3)) (proc `(,x1 ,x3 ,x2))
95 (proc `(,x2 ,x1 ,x3)) (proc `(,x2 ,x3 ,x1))
96 (proc `(,x3 ,x1 ,x2)) (proc `(,x3 ,x2 ,x1)))
97 (define (p/each4 proc x1 x2 x3 x4)
98 (p/each3 (^[xs] (proc (cons x1 xs))) x2 x3 x4)
99 (p/each3 (^[xs] (proc (cons x2 xs))) x1 x3 x4)
100 (p/each3 (^[xs] (proc (cons x3 xs))) x1 x2 x4)
101 (p/each3 (^[xs] (proc (cons x4 xs))) x1 x2 x3))
102 (define (p/each* proc len xs)
103 (if (= len 4)
104 (apply p/each4 proc xs)
105 (let1 len1 (- len 1)
106 (for-each-with-index
107 (^[ind elt]
108 (p/each* (^[subperm] (proc (cons elt subperm)))
109 len1
110 (but-kth xs ind)))
111 xs))))
112 (define (permutations-for-each proc set)
113 (match set
114 [() (undefined)]
115 [(x) (proc set)]
116 [(x1 x2) (proc `(,x1 ,x2)) (proc `(,x2 ,x1))]
117 [(x1 x2 x3) (p/each3 proc x1 x2 x3)]
118 [(x1 x2 x3 x4) (p/each4 proc x1 x2 x3 x4)]
119 [else (p/each* proc (length set) set)]))
120
121 ;; Like permutations-for-each, but considering duplications.
122 (define (permutations*-for-each proc set :optional (eq eqv?))
123 (define (rec proc set)
124 (match set
125 [() (undefined)]
126 [(a) (proc set)]
127 [(a b) (cond [(eq a b) (proc set)] [else (proc set) (proc `(,b ,a))])]
128 [else
129 (let loop ((i 0)
130 (seen '())
131 (p set))
132 (cond [(null? p)]
133 [(member (car p) seen eq) (loop (+ i 1) seen (cdr p))]
134 [else (rec (^[subperm] (proc (cons (car p) subperm)))
135 (but-kth set i))
136 (loop (+ i 1) (cons (car p) seen) (cdr p))]))]))
137 (rec proc set))
138
139 ;;----------------------------------------------------------------
140 ;; combinations
141 ;;
142
143 (define (combinations set n)
144 (define (rec set tail)
145 (cond [(null? tail) (list set)]
146 [(eq? (cdr set) tail) (map list set)]
147 [else (fold-right (cut acons (car set) <> <>)
148 (rec (cdr set) (cdr tail))
149 (rec (cdr set) tail))]))
150 (cond [(not (positive? n)) (list '())]
151 [(list-tail set n #f) => (cut rec set <>)]
152 [else '()]))
153
154 (define (combinations* set n :optional (eq eqv?))
155 (define (rec set n)
156 (if (not (positive? n))
157 (list '())
158 (let loop ((p set)
159 (seen '())
160 (r '()))
161 (cond [(null? p) (reverse! r)]
162 [(member (car p) seen eq) (loop (cdr p) seen r)]
163 [else
164 (loop (cdr p)
165 (cons (car p) seen)
166 (fold (cut acons (car p) <> <>)
167 r
168 (rec (lset-difference eq (cdr p) seen) (- n 1))))]
169 ))))
170 (rec set n))
171
172 (define (combinations-for-each proc set n)
173 (if (not (positive? n))
174 (proc '())
175 (pair-for-each
176 (^[pr]
177 (combinations-for-each
178 (^[sub-comb] (proc (cons (car pr) sub-comb)))
179 (cdr pr)
180 (- n 1)))
181 set)))
182
183 (define (combinations*-for-each proc set n :optional (eq eqv?))
184 (define (rec proc set n)
185 (if (not (positive? n))
186 (proc '())
187 (let loop ((p set)
188 (seen '()))
189 (cond [(null? p)]
190 [(member (car p) seen eq) (loop (cdr p) seen)]
191 [else
192 (rec (^[sub-comb] (proc (cons (car p) sub-comb)))
193 (lset-difference eq (cdr p) seen)
194 (- n 1))
195 (loop (cdr p) (cons (car p) seen))]))))
196 (rec proc set n))
197
198 ;;----------------------------------------------------------------
199 ;; power sets (all subsets of any size of a given set)
200 ;;
201
202 ;; the easy binary way
203 (define (power-set-binary set)
204 (if (null? set)
205 (list '())
206 (let ([x (car set)]
207 [rest (power-set-binary (cdr set))])
208 (append rest (map (^s (cons x s)) rest)))))
209
210 ;; use combinations for nice ordering
211 (define (power-set set)
212 (let ((size (length set)))
213 (let loop ((i 0))
214 (if (> i size)
215 '()
216 (append! (combinations set i)
217 (loop (+ i 1)))))))
218
219 ;; also ordered
220 (define (power-set-for-each proc set)
221 (let1 size (length set)
222 (do ([i 0 (+ i 1)])
223 [(> i size) '()]
224 (combinations-for-each proc set i))))
225
226 ;; w/o duplicate entry
227 (define (power-set* set . maybe-eq)
228 (let1 size (length set)
229 (let loop ((i 0))
230 (if (> i size)
231 '()
232 (append! (apply combinations* set i maybe-eq)
233 (loop (+ i 1)))))))
234
235 (define (power-set*-for-each proc set . maybe-eq)
236 (let1 size (length set)
237 (do ([i 0 (+ i 1)])
238 [(> i size) '()]
239 (apply combinations*-for-each proc set i maybe-eq))))
240
241 ;;----------------------------------------------------------------
242 ;; cartesian product (all combinations of one element from each set)
243 ;;
244
245 (define (cartesian-product lol)
246 (if (null? lol)
247 (list '())
248 (let ([l (car lol)]
249 [rest (cartesian-product (cdr lol))])
250 (append-map! (^x (map (^[sub-prod] (cons x sub-prod)) rest))
251 l))))
252
253 (define (cartesian-product-for-each proc lol)
254 (if (null? lol)
255 (proc '())
256 (dolist [x (car lol)]
257 (cartesian-product-for-each (^[sub-prod] (proc (cons x sub-prod)))
258 (cdr lol)))))
259
260 ;; The above is left fixed (it varies elements to the right first).
261 ;; Below is a right fixed product which could be defined with two
262 ;; reverses but is short enough to warrant the performance gain of a
263 ;; separate procedure.
264
265 ;;(define (cartesian-product-right lol)
266 ;; (map reverse (cartesian-product (reverse lol))))
267
268 (define (cartesian-product-right lol)
269 (if (null? lol)
270 (list '())
271 (let ([l (car lol)]
272 [rest (cartesian-product-right (cdr lol))])
273 (append-map! (^[sub-prod] (map (^x (cons x sub-prod)) l))
274 rest))))
275
276 (define (cartesian-product-right-for-each proc lol)
277 (if (null? lol)
278 (proc '())
279 (cartesian-product-right-for-each
280 (^[sub-prod] (for-each (^x (proc (cons x sub-prod))) (car lol)))
281 (cdr lol))))