Find the number of unordered pairs in an array

Question

I came across an interesting algorithm task:

Given an integer array, find the number of unordered pairs in this array, say, given {1, 3, 2}, answer 1, because {3, 2} is not ordered, and for the array {3, 2, 1}, answer 3 , because {3, 2}, {3, 1}, {2, 1}.

Obviously, this can be resolved by brute force with a runtime of O (n ^ 2) or rearrange all possible pairs, and then eliminate those invalid pairs.

My question is, does any solution have any solution, and how do you do it, because it seems like a dynamic programming problem. Code snippet will be useful

Answer 1

You can solve this problem O(n log n) times using a balanced binary search tree. Here is the pseudocode of this algorithm:

 tree = an empty balanced binary search tree answer = 0 for each element in the array: answer += number of the elements in the tree greater then this element add this element to the tree 

Answer 2

You can use a modified version of the merge sort to count the number of inversions. The trick is that when you merge two sorted auxiliary arrays, you can recognize elements that are inappropriate. If there are any elements in the right subarray that need to go before those in the left subarray, they are inverted. I wrote the code for this in python. You can check the explanation below to better understand. If you cannot understand the merge sort, I suggest you update the merge sort, after which it will be intuitive.

 def merge_sort(l): if len(l) <= 1: return (0, l) else: mid = len(l) / 2 count_left, ll = merge_sort(l[0:mid]) count_right, lr = merge_sort(l[mid:]) count_merge, merged = merge(ll, lr) total = count_left + count_right + count_merge return total, merged def merge(left, right): li, ri = 0, 0 merged = [] count = 0 while li < len(left) and ri < len(right): if left[li] < right[ri]: merged.append(left[li]) li += 1 else: count += 1 merged.append(right[ri]) ri += 1 if li < len(left): merged.extend(left[li:]) elif ri < len(right): merged.extend(right[ri:]) return count, merged if __name__ == '__main__': # example l = [6, 1 , 2, 3, 4, 5] print 'inverse pair count is %s'%merge_sort(l)[0] 

• Sorting sorting is done in n * log (n) time.
• for the transferred list l, merge_sort returns a tuple (in the form of (inversion_count, list)) the number of inversions and the sorted list
• The merge step counts the number of inversions and stores them in the variable counter.

Answer 3

If you are just looking for the number of an unordered pair and the array is sorted in ascending order . You can use this formula n * (n - 1) / 2. Suppose your array has n elements, for example 3 in your case. This will be 3 * 2/2 = 3. It is assumed that there are no duplicate elements.

Answer 4

You can use the modified merge sort algorithm. The merger will look something like this.

 merge(a, b): i = 0 j = 0 c = new int[a.length+b.length] inversions = 0 for(k = 0 ; k < Math.min(a.length, b.length); k++) if(a[i] > b[j]): inversions++ c[k] = b[j] j++ else: c[k] = a[i] i++ //dump the rest of the longer array in c return inversions 

Merging is performed in O (n) time. The time complexity for the entire merge sort is O (n log n)