Tag Archives: inversion

Counting inversions via rank queries

Posted on December 18, 2019 by Brent

In a post from about a year ago, I explained an algorithm for counting the number of inversions of a sequence in time. As a reminder, given a sequence , an inversion is a pair of positions such that and … Continue reading →

Posted in haskell | Tagged , , , , , , , , , | 4 Comments

Counting inversions with monoidal sparks

Posted on October 6, 2018 by Brent

Time for me to reveal the example I had in mind that led to the generalization in my previous post. Thanks for all the interesting comments: it seems like there are some interesting connections to be explored (e.g. to the … Continue reading →

Posted in math | Tagged , , , , , , , , | 8 Comments