| 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)))) |