Loading

Paste #pwquzj0pq

  1.     ;; k-combination ranking and unranking procedures according to
  2.     ;; https://en.wikipedia.org/wiki/Combinatorial_number_system
  3.  
  4.     (define (ranking lst)
  5.       (let loop ((lst (sort < lst)) ;; increasing sequence
  6.                  (k 1)
  7.                  (out 0))
  8.         (if (null? lst)
  9.             out
  10.             (loop (cdr lst) (+ k 1) (+ out (binomial-coefficient (car lst) k))))))
  11.  
  12.     (define (%unranking k N)
  13.       (let loop ((n (- k 1)))
  14.                  (if (< N (binomial-coefficient (+ n 1) k))
  15.                      n
  16.                      (loop (+ n 1)))))
  17.  
  18.     (define (unranking k N)
  19.       (let loop ((k k)
  20.                        (N N)
  21.                        (out '()))
  22.                  (if (= k 0)
  23.                      out
  24.                      (let ((m (%unranking k N)))
  25.                        (loop (- k 1) (- N (binomial-coefficient m k)) (cons m out))))))