CODEWITHSUNDEEP
algorithmpermutationswap
Yep Yep
Yep Yep

Reputation: 530

Algorithm to swap subsequences of 2 permutations

Given 2 permutations of n elements (1 to n) that are unordered, I need to check if it is possible to go from the first one to the second one using the following swapping method:

Choose a subsequence of 3 elements, lets call them (a,b,c)

You can swap them like this: (a,b,c) => (c,a,b). You can use this method an infinite number of times

For example: for the input {1,3,4,2} {4,3,2,1} it is possible

But it isn't for {1,2,3,4,5,6} {6,5,4,3,2,1}

My first approach was to take the first element from the first permutation, find it in the second one, and then simulate the swapping until the first element is the same, then do the following on every element until only 3 elements remain. then it is easy to see if it is possible to arrive from the first to the second.

But the time complexity is O(n^2) and I have to do it in O(n*log(n)) or less.

Is there any way of doing so?

Upvotes: 1

Views: 154

Answers (1)

Marat
Marat

Reputation: 15738

Let's call a case a[i] > a[j], such that i < j, a misplacement. Note that if elements are unique, a change in the number of misplacements induced by a swap (a, b, c) -> (c, a, b) is even. So, a necessary condition for such a permutation to be possible is the difference in the number of misplacements (transposition distance) has to be even.

Example:

{1,2,3,4,5,6}: 0 misplacements, {6,5,4,3,2,1}: 15 misplacements. The difference of 15 is odd, thus such permutation is not possible.

{1,3,4,2}: 2 misplacements (3 before 2, 4 before 2) {4,3,2,1}: 6 misplacements. The difference of 4 misplacements is even.

What is missing: I'm a bit lazy to formally prove this is a sufficient condition, i.e. that all even changes are possible. Also, this doesn't hold for sets with non-unique element - I'd guess any permutations are possible on those.

To calculate the number of misplacements, check Kendall tau distance algorithm. It'll need some adaptation, but will compute the distance in ~O(n log n).

Upvotes: 2

Related Questions