combinatorics

Combinatorics

  1. combinatorics
    1. Abstract
    2. Documentation
      1. ordered-subset-for-each
      2. ordered-subset-fold
      3. ordered-subset-map
      4. unordered-subset-for-each
      5. unordered-subset-fold
      6. unordered-subset-map
      7. permutation-for-each
      8. permutation-fold
      9. permutation-map
      10. combination-for-each
      11. combination-fold
      12. combination-map
    3. About this egg
      1. Author
      2. Repository
      3. License
      4. Dependencies
      5. Versions
      6. Colophon

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)

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.

Colophon

Documented by cock.