== 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}}
<procedure>(ordered-subset-for-each f list) → unspecified</procedure>
<procedure>(ordered-subset-for-each f list k) → unspecified</procedure>
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'')
<enscript highlight="scheme">(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))))))
</enscript>
==== {{ordered-subset-fold}}
<procedure>(ordered-subset-fold cons nil list) → object</procedure>
<procedure>(ordered-subset-fold cons nil list k) → object</procedure>
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'')
<enscript highlight="scheme">(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)))))
</enscript>
==== {{ordered-subset-map}}
<procedure>(ordered-subset-map f list) → list</procedure>
<procedure>(ordered-subset-map f list k) → list</procedure>
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'')
<enscript highlight="scheme">(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))))
</enscript>
==== {{unordered-subset-for-each}}
<procedure>(unordered-subset-for-each f list) → unspecified</procedure>
<procedure>(unordered-subset-for-each f list k) → unspecified</procedure>
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'')
<enscript highlight="scheme">(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)))))))))
</enscript>
==== {{unordered-subset-fold}}
<procedure>(unordered-subset-fold cons nil list) → object</procedure>
<procedure>(unordered-subset-fold cons nil list k) → object</procedure>
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'')
<enscript highlight="scheme">(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)))))
</enscript>
==== {{unordered-subset-map}}
<procedure>(unordered-subset-map f list) → list</procedure>
<procedure>(unordered-subset-map f list k) → list</procedure>
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'')
<enscript highlight="scheme">(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))))
</enscript>
==== {{permutation-for-each}}
<constant>permutation-for-each → ordered-subset-for-each</constant>
Synonym for [[#ordered-subset-for-each]]
<enscript highlight="scheme">(define permutation-for-each ordered-subset-for-each)
</enscript>
==== {{permutation-fold}}
<constant>permutation-fold → ordered-subset-fold</constant>
Synonym for [[#ordered-subset-fold]]
<enscript highlight="scheme">(define permutation-fold ordered-subset-fold)
</enscript>
==== {{permutation-map}}
<constant>permutation-map → ordered-subset-map</constant>
Synonym for [[#ordered-subset-map]]
<enscript highlight="scheme">(define permutation-map ordered-subset-map)
</enscript>
==== {{combination-for-each}}
<constant>combination-for-each → unordered-subset-for-each</constant>
Synonym for [[#unordered-subset-for-each]]
<enscript highlight="scheme">(define combination-for-each unordered-subset-for-each)
</enscript>
==== {{combination-fold}}
<constant>combination-fold → unordered-subset-fold</constant>
Synonym for [[#unordered-subset-fold]]
<enscript highlight="scheme">(define combination-fold unordered-subset-fold)
</enscript>
==== {{combination-map}}
<constant>combination-map → unordered-subset-map</constant>
Synonym for [[#unordered-subset-map]]
<enscript highlight="scheme">(define combination-map unordered-subset-map)
</enscript>
=== About this egg

==== Author

[[/users/klutometis|Peter Danenberg]]
==== Repository
[[https://github.com/klutometis/combinatorics]]
==== License
BSD
==== Dependencies
* [[hahn]]
* [[setup-helper]]
* [[vector-lib]]

==== Versions
; [[https://github.com/klutometis/combinatorics/releases/tag/0.1|0.1]] : Start with ordered-subset operations.
; [[https://github.com/klutometis/combinatorics/releases/tag/0.2|0.2]] : Add unordered subset operations.
; [[https://github.com/klutometis/combinatorics/releases/tag/0.3|0.3]] : Add documentation.
; [[https://github.com/klutometis/combinatorics/releases/tag/0.3.1|0.3.1]] : Add some tests.
; [[https://github.com/klutometis/combinatorics/releases/tag/0.3.2|0.3.2]] : Tests depend on `test'.
; [[https://github.com/klutometis/combinatorics/releases/tag/0.3.3|0.3.3]] : Actually map the values.
; [[https://github.com/klutometis/combinatorics/releases/tag/0.3.4|0.3.4]] : Add the combination- and permutation-synonyms.
; [[https://github.com/klutometis/combinatorics/releases/tag/0.3.5|0.3.5]] : Remove the dependency on setup-helper-cock.
; [[https://github.com/klutometis/combinatorics/releases/tag/0.3.6|0.3.6]] : Bump the version.
; [[https://github.com/klutometis/combinatorics/releases/tag/0.3.7|0.3.7]] : Use `use' instead of `include'.
; [[https://github.com/klutometis/combinatorics/releases/tag/0.3.8|0.3.8]] : Use hahn.
; [[https://github.com/klutometis/combinatorics/releases/tag/0.4|0.4]] : Port to C5

==== Colophon

Documented by [[/egg/hahn|hahn]].