inversion pairs in an array - application
I came 开发者_开发知识库across an algorithmic problem to find out the number of inversion pairs in an array in O(nlogn) time. I got the solution to this. But, my question is that what is the real-life application of this problem? Like I want to know some applications where we need to know the inversion pairs.
One example is the fifteen puzzle. If you want to randomly shuffle a grid of numbers, can you tell at a glance if
1 14 5 _
7 3 2 12
6 9 13 15
4 10 8 11
can be solved by sliding moves or not? The parity of the permutation will tell you that it is not.
Here is the use of inversion count in real life.. suppose you want to know how similar two list are..based on ranking.. on any movie site..two wishlist of movies are compared and few of them who are similar , are shown to users who have same choice.
Same logic applies to shopping list on any shopping website.. for recommending shopping items based on his activity..
精彩评论