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.
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')
EndThe key idea is that the rightmost maximum gives us exactly N-I inversions. We handle the rest via recursion.
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))))))
INVERSIONSLet us test:
(inversions '(1 1 1))
0
(inversions '(3 4 5 6 1 2))
8Here 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)))