You can edit this page using wiki syntax for markup.

Article contents:== Outdated egg! This is an egg for CHICKEN 4, the unsupported old release. You're almost certainly looking for [[/eggref/5/combinatorics|the CHICKEN 5 version of this egg]], if it exists. If it does not exist, there may be equivalent functionality provided by another egg; have a look at the [[https://wiki.call-cc.org/chicken-projects/egg-index-5.html|egg index]]. Otherwise, please consider porting this egg to the current version of CHICKEN. == 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. ==== Colophon Documented by [[/egg/hahn|hahn]].Description of your changes:

I would like to authenticate

Spam control

What do you get when you multiply 6 by 0?