CODEWITHSUNDEEP
algorithmcounting
Bad_at_math
Bad_at_math

Reputation: 1

Counting the number of same ordered pairs in three different permutations

I have three different permutations of the set {1,2,..n}, and I would like to write some code to count the number of pairs of numbers that come in the same order in all three permutations.

As an example with permutation of.
{1,2,3}
(1,2,3).
(3,2,1)

there are 0 such pairs where they come in the same order because (1,2,3) and (3,2,1) are sorted in both increasing and decreasing order

I want an optimal O(N*logN) solution. A hint was given, in which you have to count the number of inversions of each permutation, i.e

an inversion is the of pair (i,j) such that i > j but a[j] > a[i]

I can do this in O(NlogN).

So definitely if one pair came in the increasing order in each of the permutations it would add 1 to each inversion count for each permutation. But that isn't true if i > j and a[j] > a[i] (all came in decreasing order) as I should be increasing the count but this doesn't contribute anything to the inversion count. Also afterwards if I can count the number of inversions in each array, but I don't see a link between that and the number of same-ordered pairs.

Upvotes: 0

Views: 516

Answers (1)

ilim
ilim

Reputation: 4547

For each permutation you have, you should count the number of cases where a[i] < a[j], for each pair of indices i and j such that i < j. Let's call this non-inversions. Then, you can find out the result by taking the minimum of the non-inversion counts you found.

For instance, in your sample case, the values corresponding for the permutations (1,2,3), (1,2,3) and (3,2,1) are 3, 3, and 0, respectively.

For a different sample case, you can examine (1,2,3,4), (1,2,4,3), (1,3,2,4) and (4,1,3,2). The corresponding counts for these permutations are 6, 4, 5, and 2. The result is min(6,4,5,2) because the only tuples that remain ordered in each case are (1, 2) and (1, 3).

The key idea behind this solution is based on what non-inversion count implies. In an ordered array of size N, there are N(N-1)/2 ordered pairs contributing to the non-inversion count. As you introduce some inversions into that array, the relative order of some elements are lost, while some remain. By finding the minimum of the non-inversion counts, you can find the number of pairs that preserve their relative ordering in the 'worst' case. (even though this alone is not enough not identify them individually)

If you insist on counting the inversions (i.e. as opposed to the non-inversions) the procedure is pretty much the same. Count the inversions for each permutation given to you. Then simply subtract the maximum value you find from N(N-1)/2, and obtain the result.

Upvotes: 1

Related Questions