NZEC在INVCNT上与Guile在Spoj上

跨很长的列表进行筛选可能会使您陷入最大的错误错误（规格最多可达到一千万），而不是使用'（length（filter ...）

(define (inversion L)
 (let loop ((accumulator 0) (L L))
   (if (null? L)
       accumulator
       (loop 
         (+ accumulator
            (fold
              (lambda (init next)
                (if (> (car l) next)
                    (+ init 1)
                    init))
              0
              (cdr L)))
         (cdr L)))))

其次，虽然这会更容易阅读，但可以将其折叠成自己的功能

(define (inversions-from-car L)
  (fold
     (lambda (init next)
        (if (> (car l) next)
            (+ init 1)
            init))
      0
      (cdr L)))

(define (inversion L)
 (let loop ((accumulator 0) (L L))
   (if (null? L)
       accumulator
       (loop 
         (+ accumulator
             (inversions-from-car L)     
         (cdr L)))))

看起来像处理数据结构是一个好问题，因为按照书面形式，它的复杂度为n ^ 2。

我认为您可以将其降低到n（log n）

假设在值列表上创建一个排序树，并与左侧的＃个节点配对。对于这套

'(2 3 8 6 1) -> '(1 2 3 6 8) -> 
(*tree (*entry 3 2 2)
       (*tree (*entry 2 1 1)
              (*tree (*entry 1 0 1)
                     ()
                     ())
              ())
        (*tree (*entry 8 1 1)
               (*tree (*entry 6 0 1)
                      ()
                      ())
               ()))      

* tree和* entry只是类型年龄* tree应该有一个条目，左边和右边* entry应该有一个值，＃left和number）

首先用零累加器在原始列表中找到FIRST

'（2 3 8 6 1）

如果enrty的值与FIRST匹配，则将#left添加到累加器

如果值为entry大于带有累加器的树的左分支上的FIRST递归

如果条目的值小于FIRST，则向右分支递归，将#left添加到累加器

如果是空树则抛出错误

然后，您需要更新树。

如果该条目的值等于FIRST，请对该条目进行突变以将其数量减一

如果该值是entry大于FIRST，则对该条目进行突变以将#left减1，然后在左侧分支上递归

如果条目的值小于first，则在右分支上递归

如果是空树则抛出错误

您可以将这些规则组合成一个遍历

另外添加以下规则：如果#left为0且number为零，则如果right分支为null，则将此树更改为空树，否则将其右分支。

这是一个粗略（想法的未经测试的版本）

(define (rev-sorted-list->count-list L) ;;sort should be resverse of
                                        ;; final desired order
 (let loop ((value (car L)) (count 1) (L (cdr L)) (acc '()))
   (cond ((null? L) '())
         ((= value (car l))
          (loop value (+ 1 count) (cdr L) acc))
         (else 
          (loop (car l) 1 (cdr L) (cons (cons value count) acc))))))

(define (make-tree count c-L)
 (let* ((middle (ceiling (+ 1 count) 2))
        (left-count (- middle 1))
        (right-count (-count middle))
        (left (if (= 0 left-count)
                  null-tree 
                  (make-tree left-count c-L)))
        (entry+right
          (let loop ((index 1) (L c-L))
            (if (= index middle) 
                L
                (loop (+ 1 index) (cdr L)))))
        (entry 
         (make-entry 
           (caar entry+right)
           left-count
           (cdar entry+right))))
    (build-tree 
       entry
       left
       (if (= 0 right-count)
           null-tree
           (make-tree right-count (cdr entry+right))))))     

;;form left branches from starting points
;;;form right from stopping points
;;never mutating c-L or copies

;;if count = 0 then null tree

(define (build-tree entry left right)
  (list '*tree entry left right) 

(define (entry tree)
 (cadr tree)
(define (left-branch tree)
 (caddr tree))
(define (right-branch tree)
 (cadddr tree))

(define null-tree (list '*tree '()))
(define (null-tree? tree)
 (null? (entry tree)))

(define (make-entry value Nleft count)
 (let ((vec (make-vector 3)))
  (begin (vector-set! vec 0 value)
         (vector-set! vec 1 Nleft)
         (vector-set! vec 2 count)
         vec)))

;;might meessage passing function here

(define (entry-value entry)
 (vector-ref entry 0))

(define (entry-Nleft entry)
 (vector-ref entry 1))

(define (entry-Nleft-set! entry int)
 (vector-set! entry 1 int))

(define (entry-count entry)
 (vector-ref entry 2))

(define (entry-count-set! entry int)
 (vector-set! entry 2 int))

(define (inversions! Test-List Search-Tree)
 (let loop ((acc 0) (L Test-list) (T Search-tree))
   (cond ((null? L) acc)
         ((null-tree? T) (error "null tree " 
                                 "in inner loop of inversion!"))
         ((= (car L) (entry-value (entry T)))
          (entry-count-set! (entry T)
                            (- (entry-count (entry T)) 1))
          (if (and (= 0 (entry-count (entry T)))
                   (= 0 (entry-Nleft (entry T))))
               (set-cdr! T (right-branch T))
               'skip)
          (loop (+ acc (entry-Nleft (entry T)))
                (cdr L)
                Search-tree))
         ((< (car L) (entry-value (entry T)))
          (entry-Nleft-set! (entry T)
                            (- (entry-Nleft (entry T)) 1))
          (loop acc L (left-branch T)))
         ((> (car L) (entry-value (entry T)))
          (loop (+ acc (entry-Nleft (entry T)))
                L
                (right-branch T))))))