right greater-thans

Write a function accepting a list of integers l and returning a list of integer c such that the ith element of c equals the number of elements in l that are to the right of the ith element of l and greater than that element (that is, c[i] = #(l[i] < l[j] : i < j < |l|).

 $ cat rgc.rkt  
 #lang racket 
  
  
 (define (rgc-l l) 
  
   ; Given the integer list l, return an integer list c where 
   ; c[i] equals the number of elements in l(i..|l|) that are 
   ; greater than l[i]. 
  
   (let loop ((l l) (c '())) 
  
     (if (null? l) 
  
       (reverse c) 
  
       (let* 
  
         ((e (car l)) 
          (l (cdr l)) 
          (cnt (foldr (lambda (e2 c) (if (< e e2) (+ c 1) c)) 
                      0 l))) 
  
         (loop l (cons cnt c)))))) 
  
  
 (define (rgc-v l) 
  
   ; Given the integer list l, return an integer list c where 
   ; c[i] equals the number of elements in l(i..|l|) that are 
   ; greater than l[i]. 
  
   (if (null? l) 
     '() 
     (let* 
  
       ((v (list->vector l)) 
        (n (length l)) 
        (cnts (make-vector n))) 
  
       (vector->list  
         (do ((i (- n 1) (- i 1))) ((< i 0) cnts) 
  
         (let* 
  
           ((e (vector-ref v i)) 
            (c 0) 
            (cnt (do ((j (+ i 1) (+ j 1))) ((= j n) c) 
                   (when (< e (vector-ref v j)) 
                     (set! c (+ c 1)))))) 
  
           (vector-set! cnts i cnt))))))) 
  
  
 (module+ test 
  
   (require rackunit "utl.rkt") 
  
   (define (run-test f) 
     (check-equal? (f '()) '()) 
     (check-equal? (f '(1)) '(0)) 
     (check-equal? (f '(1 2)) '(1 0)) 
     (check-equal? 
       (f '(10 12 8 17 3 24 19)) '(4 3 3 2 2 0 0))) 
  
   (run-test rgc-v) 
   (run-test rgc-l) 
  
   (do ((i 0 (+ i 1))) ((= i 100) (void)) 
     (let ((l (random-list (random 100)))) 
       (check-equal? (rgc-v l) (rgc-l l)))) 
  
  
   (define (time-it f n iters seed) 
      
     (random-seed seed) 
  
     (let loop ((t 0) (i 0)) 
       (if (= i iters) 
         (inexact->exact (round (/ t iters)))       
         (let ((l (random-list n))) 
           (let-values 
             (((a b c d) (time-apply f (list l)))) 
             (loop (+ t b) (+ i 1))))))) 
  
   (let ((iters 10)) 
     (do ((i 1000 (+ 1000 i))) ((> i 10000) (void)) 
       (printf "n: ~a, rgc-l: ~a, rgc-v: ~a\n" 
         i 
         (time-it rgc-l i iters i) 
         (time-it rgc-v i iters i)))) 
   ) 
  
 $ raco test rgc.rkt  
 raco test: (submod "rgc.rkt" test) 
 n: 1000, rgc-l: 19, rgc-v: 8 
 n: 2000, rgc-l: 75, rgc-v: 30 
 n: 3000, rgc-l: 171, rgc-v: 66 
 n: 4000, rgc-l: 314, rgc-v: 118 
 n: 5000, rgc-l: 549, rgc-v: 184 
 n: 6000, rgc-l: 878, rgc-v: 269 
 n: 7000, rgc-l: 1339, rgc-v: 368 
 n: 8000, rgc-l: 1862, rgc-v: 478 
 n: 9000, rgc-l: 2430, rgc-v: 604 
 n: 10000, rgc-l: 3077, rgc-v: 733 
 108 tests passed 
  
 $