You are looking at historical revision 29928 of this page. It may differ significantly from its current revision.

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

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.

Colophon

Documented by cock.