12.5. Graphical Representation of Inversions

So, we can formulate this in another way. So, now, we take our ranking and we assume that is the given order. So, we pick the certain order for the movies and we call that the basic ranking 1, 2, 3, 4 up to n. Now, our friend's ranking would rank what we called 1 as maybe 5, what we call 2 is maybe 3 and so on. So, everything that we rank with a rank i will be ranked where different rank j by our friend and of course, every rank will appear there somewhere are the other.

So, the friend's ranking will be a permutation of 1 to n and what you are asking is if I rank i before j, that is before i is the smaller number than j, does the friend rank j before i, any such think would be an inversion. So, inversion would be a pair i comma j in my list, where i smaller than j. So, my list i is update of j, but in my friend's list, j appears before i in the add permutation.

In this chunk, we define what an inversion is in the context of ranking preferences. We start by establishing a basic ranking for items (like movies) from 1 to n. We then consider how a friend's ranking could be a different arrangement of these items. If we say we prefer movie i over movie j (i < j) but our friend prefers movie j over i, this contradiction represents an inversion. Inversions are a measure of dissimilarity between our ranking and our friend’s ranking. Thus, the more inversions there are, the more our preferences differ.

Imagine you and a friend are picking where to eat for dinner. You prefer Italian food (let's say you rank it as your number one choice), while your friend prefers Chinese food as their top choice. If you both list your preferences, and you rank Italian first while your friend ranks it last, this creates an inversion in your preferences. The more disagreements you have on your favorite restaurants, the more inversions you have, indicating you might want to take turns or find a middle-ground restaurant that you both like.

So, another way of thinking about this, though it will not materially affect how we compute it, is to draw this kind of a graph. So, you take the rankings to start with as the correct order on top. So, you have one set of vertices 1 to 5 and then, you have to permutation of the vertices 1 to 5 listed in the order of your friend's ranking. And then, you combine 1 to 1, 2 to 2 and so on, so that you build up in the graph which as if you have 5 on top and 5 in the bottom, you have 5 edges, if you have n and n you have n edges.

Now, in this graph every time a line crosses this indicates a mismatch, so 2 has a gone ahead of 1, likewise 4 is gone ahead of 3 and so on. So, there are 4 crossing is between these lines and that really corresponds to four inversions in this example.

In this chunk, we introduce a visual representation of inversions through a graphical model. By plotting our rankings as a vertical line (the correct order) and our friend's rankings as a line below it, we can see the relationships between the rankings. Each crossing line between our ranking and our friend's ranking symbolizes an inversion, identifying an instance where the order of preference differs. For example, if our preference for item 2 is before item 1, but our friend's preference has item 1 before item 2, that crossing represents an inversion.

Think of a race where two runners, Alice and Bob, are competing. You can visually graph their finishing positions where the top row shows Alice's times and the bottom shows Bob's. If they finish in the order Alice, Bob, Charlie, but on Bob's side it reads Charlie, Alice, Bob, then where Alice finishes ahead of Charlie but Bob finishes behind him shows clear lines intersecting on the graph. Each intersection indicates a disagreement about who is faster (the order of preference), similarly representing the inversions in your rankings.

So, our whole is to give a more efficient algorithm, so we will move to this divide and conquer paradigm. So, suppose your friend’s permutation, our permutation always 1 to n, so we can just assume it is given. So, what is early interesting is our friends permutation, so the friends permutation is some order of 1 to n jumbled up, let us call it i 1 to i n. So, now, we will do something similar to merge sort, so you will take this list i 1 to i n and divide in two parts.

So, we have i 1 to i n by 2 which is the left and i n by 2 plus 1 to n which is the right. So, divide and conquer is a very simple minded strategy, you can only do one thing, you can solve this and then, you can combine. So, this is the basic paradigm, so you have to divide, solve the divided parts and combine.

In this chunk, we discuss how to efficiently count inversions using the divide and conquer approach, similar to how merge sort works. Instead of looking at every single pair (which could take a lot of time), we can divide the permutation into two halves, recursively count inversions in both halves, and then merge them back. During the merging process, we also count how many of the items from the right are less than those in the left, which indicates additional inversions across the split boundaries.

Imagine a group of friends who want to order food, and it's too chaotic to just list preferences at once. Instead, you decide to have the group split—one half discusses what they want while the other half does the same. After each subgroup has come up with their preferred items, you can combine both lists. While doing this, you might realize that someone from one group really dislikes a choice favored by another, indicating more inversions. This is like merging sorted lists and counting inversions efficiently without having to compare every single preference manually.

--