Inversions in a sequence of numbers

This post is about counting the number of “inversions” in a sequence of numbers. A concept useful in linear algebra when computing the determinant of a matrix.

Problem Statement
By an inversion in a sequence of numbers x1, x2, … xn we mean an arrangement of two indices such that the larger index comes before the smaller index. Let us denote the total number of inversions by a function N. For example, in the permutation 2, 1 4, 3 there are two inversions (2 before 1, 4 before 3), so that

N(2, 1, 4, 3) = 2

In the permutation 4, 3, 1, 2, there are five inversions (4 before 3, 4 before 1, 4 before 2, 3 before 1, 3 before 2), so that

N(4, 3, 1, 2) = 5

The general solution to this problem is to sequence through each number in the list and compare it with the remaining numbers. Starting with an initial count of zero, in each comparison we increment the count if we detect an out of sequence set of numbers. Given the list [2 1 4 3] the algorithm should:

  • Pick the first number 2 and compare it with each number in the remaining list [1 4 3]. Count incremented to 1 (since we see only one out of order sequence.
  • Pick next number 1 and compare it with each number in the remaining list [4 3]. Count unchanged
  • Pick 4 and compare it with each number in the remaining list [3]. Count incremented to 2.
  • Pick 3 and compare it with the remaining list [] which is now empty. The empty list ends the algorithm and total count of 2 is returned.

Let us try to build the solution step by step and evolve it along.

Solution
The first building block will be a function that takes a list of numbers [xs] and compares the first with the remaining list of numbers (rest xs) – counting the inversions for each comparison. This function will have to be called repetitively as we progress through the list.

(defn cnt-inv [xs]
   (map #(> (first xs) %) (rest xs)))

;refactor using let to capture first number
(defn cnt-inv [xs]
  (let [x (first xs)]
     (map #(> x %) (rest xs))))

;use partial to clean up the function inside map:
(defn cnt-inv [xs]
  (let [x (first xs)]
     (map (partial > x) (rest xs))))

The function cnt-inv returns a list of booleans – “true” for out of order sequence, otherwise a “false”.

exp.inversion=> (cnt-inv '(2 1 4 3))
(true false false)

We are interested in the number of “true” values, so let’s modify the function to give us that.

(defn cnt-inv [xs]
  (if (seq xs)
    (let [x (first xs)]
      (count (filter true? (map (partial > x) (rest xs)))))
    0))

This function can be made a bit more readable by using destructuring for the arguments which makes our intent to use it more clear. Note the extra square parenthesis in the argument as a result of destructuring. The function still takes a list as an argument but now the first element will automatically be assigned to “x” and the rest of the list to “more”:

(defn cnt-inv [[x & more]]
  (if (seq more)
    (count (filter true? (map (partial > x) more)))
    0))

;If the sequence is empty the count will return 0,
;so we can remove the if condition:
(defn cnt-inv [[x & more]]
  (count (filter true? (map (partial > x) more))))

Invoking the function produces the right count:

exp.inversion=> (cnt-inv '(2 1 4 3))
1
exp.inversion=> (cnt-inv '(1 4 3))
0
exp.inversion=> (cnt-inv '(4 3))
1
exp.inversion=> (cnt-inv '(3))
0
exp.inversion=> (cnt-inv '())
0

Next step in the algorithm is to invoke the function cnt-inv repetitively with a diminishing list of numbers and count all the inversions. We can write such a function that takes an extra argument “count”. This function is kicked off with an initial count of zero:

(defn inversions [xs count]
  (if (seq xs)
    (recur (next xs) (+ count (cnt-inv xs)))
     count))

The above function provides the desired result however we have to always invoke it with an extra argument (count) initialized to 0:

exp.inversion=> (inversions '(2 1 4 3) 0)
2
exp.inversion=> (inversions '(4 3 1 2) 0)
5

To avoid the extra argument, the function can be re-written to use the loop construct as follows:

(defn inversions [xs]
  (loop [xs xs count 0]
    (if (seq xs)
      (recur (next xs) (+ count (cnt-inv xs)))
       count)))

Further elegance
Can we simplify this further? What are we essentially doing? Given a list such as ‘(2 1 4 3) we are performing operations (cnt-inv) on:

(2 1 4 3)
(1 4 3)
(4 3)
(3)

We could generate the above lists using the rest function repeatedly on our original input sequence. Clojure provides the iterate function just to do this. However it produces an infinite lazy sequence so we need to take only the ones that are not-empty:

exp.inversion=> (def xs '(2 1 4 3))
#'exp.inversion/xs

exp.inversion=> (take-while #(not (empty? %)) (iterate rest xs))
((2 1 4 3) (1 4 3) (4 3) (3))

;#(not (empty? %)) is equivalent to => seq function
exp.inversion=> (take-while seq (iterate rest xs))
((2 1 4 3) (1 4 3) (4 3) (3))

Now we can apply the function cnt-inv on the lists generated above and sum up all the values returned by the invocations:

(defn inversions [xs]
  (apply +
    (map cnt-inv (take-while seq (iterate rest xs)))))

Finally, we can inline the definition of cnt-inv and the entire function can now be written elegantly as:

(defn inversions [xs]
  (apply +
     (map (fn [[x & more]]
            (count (filter true? (map (partial > x) more))))
        (take-while seq (iterate rest xs)))))

Comments?

Programming , Leave a comment