Write a function accepting an integer list l and returning pl, a permutation of l. The ith element in pl has the ith largest gap among the elements in pl.
$ cat dgs.rkt #lang racket (require rnrs/sorting-6 rackunit "utl.rkt") (define (dgs l) ; Return a premutation pl of the integer list l. The integers ; in pl are sorted by decreasing gap size. The gap of the ith ; element e in pl is the difference between e and e's successor ; when l is sorted in decreasing order. The last element in pl ; has gap 0. (define (deltas v) ; Return vector d. d[i] = v[i] - v[i + 1] but ; d[n - 1] = 0, n = |v|. |v| > 0 assumed. (let* ((n (vector-length v)) (d (make-vector n))) (vector-set! d (- n 1) 0) (do ((i (- n 2) (- i 1))) ((< i 0) d) (vector-set! d i (- (vector-ref v i) (vector-ref v (+ i 1))))))) (let* ((v (vector-sort > (list->vector l)))) (vector->list (vector-map car (vector-sort (lambda (a b) (> (cdr a) (cdr b))) (vector-map cons v (deltas v))))))) (let ((l '(5 12 14 15 80 121 134 144 256)) (gs '(256 80 121 134 144 12 14 15 5))) (check-equal? (dgs l) gs)) (do ((i 1 (+ i 1))) ((> i 10)) (let ((f (fibonacci i))) (check-equal? (dgs (permute-list f)) (reverse f)))) $ mzscheme dgs.rkt $