You are looking at historical revision 29928 of this page. It may differ significantly from its current revision.
combinatorics
Combinatorics
Abstract
Combinatorics provides some mechanisms for iterating over, reducing and mapping permutations (ordered subsets) and combinations (unordered subsets) of lists.
Combinatorics supports partial, i.e. k-permutations and partial, i.e. k-combinations.
Documentation
ordered-subset-for-each
[procedure] (ordered-subset-for-each f list) → unspecified[procedure] (ordered-subset-for-each f list k) → unspecified
Iterate over every k-permutation (partial ordered subset) of list, calling f for its side effect.
- f
- The function to call
- list
- The list to permute
- k
- k distinct elements (default: n)
(define ordered-subset-for-each
(case-lambda
((f list) (ordered-subset-for-each f list (length list)))
((f list k)
(let iter ((list list) (k k) (subset '()))
(if (zero? k)
(f subset)
(for-each
(lambda (element)
(iter (delete element list) (sub1 k) (cons element subset)))
list))))))
ordered-subset-fold
[procedure] (ordered-subset-fold cons nil list) → object[procedure] (ordered-subset-fold cons nil list k) → object
Recombine every k-permutation (partial ordered subset) of list, starting with a base-case nil, and calling cons with 1. a permutation and 2. the accumulated value.
- cons
- The combining function
- nil
- The base case
- list
- The list to recombine
- k
- k distinct elements (default: n)
(define ordered-subset-fold
(case-lambda
((cons nil list) (ordered-subset-fold cons nil list (length list)))
((cons nil list k)
(let ((nil (make-parameter nil)))
(ordered-subset-for-each
(lambda (subset) (nil (cons subset (nil))))
list
k)
(nil)))))
ordered-subset-map
[procedure] (ordered-subset-map f list) → list[procedure] (ordered-subset-map f list k) → list
Map every k-permutation (partial ordered subset) of list using f.
- f
- The mapping function
- list
- The list to map
- k
- k distinct elements (default: n)
(define ordered-subset-map
(case-lambda
((f list) (ordered-subset-map f list (length list)))
((f list k)
(ordered-subset-fold (lambda (v a) (cons (f v) a)) '() list k))))
unordered-subset-for-each
[procedure] (unordered-subset-for-each f list) → unspecified[procedure] (unordered-subset-for-each f list k) → unspecified
Iterate over every k-combination (partial unordered subset) of list, calling f for its side effect.
- f
- The function to call
- list
- The list to permute
- k
- k distinct elements (default: n)
(define unordered-subset-for-each
(case-lambda
((f list) (unordered-subset-for-each f list (length list)))
((f list k)
(let ((subset (make-vector k)) (n (length list)))
(let iter ((start 0) (p 0))
(if (= p k)
(f (project subset list))
(do ((i start (+ i 1)))
((= i n))
(vector-set! subset p i)
(iter (add1 i) (add1 p)))))))))
unordered-subset-fold
[procedure] (unordered-subset-fold cons nil list) → object[procedure] (unordered-subset-fold cons nil list k) → object
Recombine every k-combination (partial unordered subset) of list, starting with a base-case nil, and calling cons with 1. a combination and 2. the accumulated value.
- cons
- The combining function
- nil
- The base case
- list
- The list to recombine
- k
- k distinct elements (default: n)
(define unordered-subset-fold
(case-lambda
((cons nil list) (unordered-subset-fold cons nil list (length list)))
((cons nil list k)
(let ((nil (make-parameter nil)))
(unordered-subset-for-each
(lambda (subset) (nil (cons subset (nil))))
list
k)
(nil)))))
unordered-subset-map
[procedure] (unordered-subset-map f list) → list[procedure] (unordered-subset-map f list k) → list
Map every k-combination (partial unordered subset) of list using f.
- f
- The mapping function
- list
- The list to map
- k
- k distinct elements (default: n)
(define unordered-subset-map
(case-lambda
((f list) (unordered-subset-map f list (length list)))
((f list k)
(unordered-subset-fold (lambda (v a) (cons (f v) a)) '() list k))))
About this egg
Author
Repository
https://github.com/klutometis/combinatorics
License
BSD
Dependencies
Versions
- 0.1
- Start with ordered-subset operations.
- 0.2
- Add unordered subset operations.
- 0.3
- Add documentation.
- 0.3.1
- Add some tests.
- 0.3.2
- Tests depend on `test'.
- 0.3.3
- Actually map the values.
Colophon
Documented by cock.