[Chicken-users] Re: Chase's Sequence - syntax fixes, examples, anagram index

[Tobia Conforto]

metaperl.j wrote:
> My goal is to be able to return a unique whole number indicating which
> permutation of n items was input.

You mean something like this?

>-----------------------------------------------------------------------
(use srfi-1)

;; why is this not in srfi-1
(define (position item lst)
  (list-index (lambda (x) (equal? x item)) lst))

(define (permutation-index permuted original)
  (let loop ((sum 0)
             (perm permuted)
             (orig original)
             (radix (length permuted)))
    (if (null? perm)
        sum
        (let ((elem (car perm)))
          (loop (+ (* radix sum)
                   (position elem orig))
                (cdr perm)
                (delete elem orig)
                (- radix 1))))))

(define (anagram-index anagram)
  (let ((original (sort anagram <)))
    (permutation-index anagram original)))

(anagram-index '(1 2 3)) ;=> 0
(anagram-index '(1 3 2)) ;=> 1
(anagram-index '(2 1 3)) ;=> 2
(anagram-index '(2 3 1)) ;=> 3
(anagram-index '(3 1 2)) ;=> 4
(anagram-index '(3 2 1)) ;=> 5
>-----------------------------------------------------------------------

See http://en.wikipedia.org/wiki/Factoradic for info on how it works.


Tobia