chickadee » combinatorics

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 »