The Number of Inversions in a Sequence

Description of the problem

Assume \((a_n)\) is a sequence of integers. An inversion in \((a_n)\) is a pair of integers \(a_i\) and \(a_j\) appearing in \((a_n)\) such that \(i < j\) but \(a_i \> a_j\). Today, I will describe an algorithm which will give us the number of inversions in a finite sequence of integers.

Algorithm

Out algorithm is going to be recursive:

Algorithm Inversions:
Input: A finite sequence SEQ
Output: Number of inversions in SEQ
Begin
  Let N be the length of SEQ
  Let M be the maximum of all elements of SEQ
  Let I be the position of the rightmost 
      appearence of M in SEQ
  Let SEQ' be the SEQ from which the rightmost
      maximum is removed
  Return N - I + Inversions(SEQ')
End

The key idea is that the rightmost maximum gives us exactly N-I inversions. We handle the rest via recursion.

Code

I will give below a tail recursive version of the algorithm I described above

(defun inversions (seq &optional (res 0))
   (if (= (length seq) 1)
      res
      (let* ((n (length seq))
             (m (apply #'max seq))
             (i (position m seq :from-end 0))
             (seq2 (append (subseq seq 0 i) (subseq seq (1+ i)))))
         (inversions seq2 (+ res (- n i 1))))))

INVERSIONS

Let us test:

(inversions '(1 1 1))

0

(inversions '(3 4 5 6 1 2))

8

Here is the list of the number of inversions for each permutation on 5 letters:

(defun all-permutations (n)
   (if (= n 1)
       (list (list 1))
       (mapcan (lambda (seq)
                  (let (res)
                     (dotimes (i n res)
                        (push (nconc (subseq seq 0 i)
                                     (cons n (subseq seq i)))
                              res))))
               (all-permutations (1- n)))))

ALL-PERMUTATIONS

(mapcar (lambda (x) (list (inversions x) x)) (all-permutations 5))

((0 (1 2 3 4 5)) (1 (1 2 3 5 4)) (2 (1 2 5 3 4)) (3 (1 5 2 3 4))
 (4 (5 1 2 3 4)) (1 (1 2 4 3 5)) (2 (1 2 4 5 3)) (3 (1 2 5 4 3))
 (4 (1 5 2 4 3)) (5 (5 1 2 4 3)) (2 (1 4 2 3 5)) (3 (1 4 2 5 3))
 (4 (1 4 5 2 3)) (5 (1 5 4 2 3)) (6 (5 1 4 2 3)) (3 (4 1 2 3 5))
 (4 (4 1 2 5 3)) (5 (4 1 5 2 3)) (6 (4 5 1 2 3)) (7 (5 4 1 2 3))
 (1 (1 3 2 4 5)) (2 (1 3 2 5 4)) (3 (1 3 5 2 4)) (4 (1 5 3 2 4))
 (5 (5 1 3 2 4)) (2 (1 3 4 2 5)) (3 (1 3 4 5 2)) (4 (1 3 5 4 2))
 (5 (1 5 3 4 2)) (6 (5 1 3 4 2)) (3 (1 4 3 2 5)) (4 (1 4 3 5 2))
 (5 (1 4 5 3 2)) (6 (1 5 4 3 2)) (7 (5 1 4 3 2)) (4 (4 1 3 2 5))
 (5 (4 1 3 5 2)) (6 (4 1 5 3 2)) (7 (4 5 1 3 2)) (8 (5 4 1 3 2))
 (2 (3 1 2 4 5)) (3 (3 1 2 5 4)) (4 (3 1 5 2 4)) (5 (3 5 1 2 4))
 (6 (5 3 1 2 4)) (3 (3 1 4 2 5)) (4 (3 1 4 5 2)) (5 (3 1 5 4 2))
 (6 (3 5 1 4 2)) (7 (5 3 1 4 2)) (4 (3 4 1 2 5)) (5 (3 4 1 5 2))
 (6 (3 4 5 1 2)) (7 (3 5 4 1 2)) (8 (5 3 4 1 2)) (5 (4 3 1 2 5))
 (6 (4 3 1 5 2)) (7 (4 3 5 1 2)) (8 (4 5 3 1 2)) (9 (5 4 3 1 2))
 (1 (2 1 3 4 5)) (2 (2 1 3 5 4)) (3 (2 1 5 3 4)) (4 (2 5 1 3 4))
 (5 (5 2 1 3 4)) (2 (2 1 4 3 5)) (3 (2 1 4 5 3)) (4 (2 1 5 4 3))
 (5 (2 5 1 4 3)) (6 (5 2 1 4 3)) (3 (2 4 1 3 5)) (4 (2 4 1 5 3))
 (5 (2 4 5 1 3)) (6 (2 5 4 1 3)) (7 (5 2 4 1 3)) (4 (4 2 1 3 5))
 (5 (4 2 1 5 3)) (6 (4 2 5 1 3)) (7 (4 5 2 1 3)) (8 (5 4 2 1 3))
 (2 (2 3 1 4 5)) (3 (2 3 1 5 4)) (4 (2 3 5 1 4)) (5 (2 5 3 1 4))
 (6 (5 2 3 1 4)) (3 (2 3 4 1 5)) (4 (2 3 4 5 1)) (5 (2 3 5 4 1))
 (6 (2 5 3 4 1)) (7 (5 2 3 4 1)) (4 (2 4 3 1 5)) (5 (2 4 3 5 1))
 (6 (2 4 5 3 1)) (7 (2 5 4 3 1)) (8 (5 2 4 3 1)) (5 (4 2 3 1 5))
 (6 (4 2 3 5 1)) (7 (4 2 5 3 1)) (8 (4 5 2 3 1)) (9 (5 4 2 3 1))
 (3 (3 2 1 4 5)) (4 (3 2 1 5 4)) (5 (3 2 5 1 4)) (6 (3 5 2 1 4))
 (7 (5 3 2 1 4)) (4 (3 2 4 1 5)) (5 (3 2 4 5 1)) (6 (3 2 5 4 1))
 (7 (3 5 2 4 1)) (8 (5 3 2 4 1)) (5 (3 4 2 1 5)) (6 (3 4 2 5 1))
 (7 (3 4 5 2 1)) (8 (3 5 4 2 1)) (9 (5 3 4 2 1)) (6 (4 3 2 1 5))
 (7 (4 3 2 5 1)) (8 (4 3 5 2 1)) (9 (4 5 3 2 1)) (10 (5 4 3 2 1)))