== combinatorics
Combinatorics
[[toc:]]
=== 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}}
(ordered-subset-for-each f list) → unspecified
(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}}
(ordered-subset-fold cons nil list) → object
(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}}
(ordered-subset-map f list) → list
(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}}
(unordered-subset-for-each f list) → unspecified
(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}}
(unordered-subset-fold cons nil list) → object
(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}}
(unordered-subset-map f list) → list
(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
[[/users/klutometis|Peter Danenberg]]
==== Repository
[[https://github.com/klutometis/combinatorics]]
==== License
BSD
==== Dependencies
* [[cock]]
* [[setup-helper]]
* [[vector-lib]]
==== 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'.
==== Colophon
Documented by [[/egg/cock|cock]].