chickadee » combinatorics

Outdated egg!

This is an egg for CHICKEN 4, the unsupported old release. You're almost certainly looking for 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 egg index. Otherwise, please consider porting this egg to the current version of CHICKEN.

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

ordered-subset-for-each f listprocedure
ordered-subset-for-each f list kprocedure

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 listprocedure
ordered-subset-fold cons nil list kprocedure

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 listprocedure
ordered-subset-map f list kprocedure

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 listprocedure
unordered-subset-for-each f list kprocedure

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 listprocedure
unordered-subset-fold cons nil list kprocedure

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 listprocedure
unordered-subset-map f list kprocedure

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

permutation-for-each

permutation-for-eachconstant

Synonym for ordered-subset-for-each

(define permutation-for-each ordered-subset-for-each)

permutation-fold

permutation-foldconstant

Synonym for ordered-subset-fold

(define permutation-fold ordered-subset-fold)

permutation-map

permutation-mapconstant

Synonym for ordered-subset-map

(define permutation-map ordered-subset-map)

combination-for-each

combination-for-eachconstant

Synonym for unordered-subset-for-each

(define combination-for-each unordered-subset-for-each)

combination-fold

combination-foldconstant

Synonym for unordered-subset-fold

(define combination-fold unordered-subset-fold)

combination-map

combination-mapconstant

Synonym for unordered-subset-map

(define combination-map unordered-subset-map)

About this egg

Author

Peter Danenberg

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.
0.3.4
Add the combination- and permutation-synonyms.
0.3.5
Remove the dependency on setup-helper-cock.
0.3.6
Bump the version.
0.3.7
Use `use' instead of `include'.
0.3.8
Use hahn.

Colophon

Documented by hahn.

Contents »