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`

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

`permutation-for-each`

[constant] permutation-for-each → ordered-subset-for-each

Synonym for ordered-subset-for-each

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

`permutation-fold`

[constant] permutation-fold → ordered-subset-fold

Synonym for ordered-subset-fold

(define permutation-fold ordered-subset-fold)

`permutation-map`

[constant] permutation-map → ordered-subset-map

Synonym for ordered-subset-map

(define permutation-map ordered-subset-map)

`combination-for-each`

[constant] combination-for-each → unordered-subset-for-each

Synonym for unordered-subset-for-each

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

`combination-fold`

[constant] combination-fold → unordered-subset-fold

Synonym for unordered-subset-fold

(define combination-fold unordered-subset-fold)

`combination-map`

[constant] combination-map → unordered-subset-map

Synonym for unordered-subset-map

(define combination-map unordered-subset-map)

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.