thematdev's blog

Linear time algorithm for parity of permutation, around 1591D
By thematdev, 3 years ago, In English

This blog is inspired by problem 1591D - Yet Another Sorting Problem, hope you will enjoy it.

Basic concepts

First of all, let's define some basic things, you can skip it if you know it.

Parity of permutation $$$p$$$ is parity of number of inversions in it. Inversion is pair $$$(i, j)$$$ such that $$$i < j, p_i > p_j$$$.

Composition of permutations defined as follows $$$(f \circ g)_x = f_{g_x}$$$, we first apply $$$g$$$, then $$$f$$$.

Cycle is a permutation, where some indices are cyclic shifted, for example $$$p = \begin{pmatrix}1 & 5 & 2 & 4 & 3\end{pmatrix}$$$ is a cycle $$$\begin{pmatrix}2 & 3 & 5\end{pmatrix}$$$.

Theorem. Every permutation is composition of non-intersecting cycles.

Proof. Consider directed graph where vertices are numbers from $$$1$$$ to $$$n$$$, and edges are $$$i \to p_i$$$ for all $$$i$$$. Since $$$p$$$ is permutation, indegree and outdegree of each vertex is 1, hence our graph is collection of cycles, that's what we want.

Lemma. Applying swap to permutation will change its parity.

This lemma is very important, so it is left to reader as an exercise.

Fact. Parity of $$$(f \circ g)$$$ is sum of parities of $$$f$$$ and $$$g$$$.

Proof. Applying swap to permutation change its parity, thus if permutation $$$f$$$ can be represented as $$$k$$$ swaps, then parity of $$$k$$$ is parity of $$$f$$$. So if $$$f$$$ can be represented as $$$k$$$ swaps, and $$$g$$$ can be represented as $$$m$$$ swaps, then $$$f \circ g$$$ can be represented as $$$k + m$$$ swaps, but parity of $$$f \circ g$$$ is parity of $$$k + m$$$, which is sum of parities of $$$f$$$ and $$$g$$$, QED.

Counting inversions, parity of permutation

There are many ways to count number of inversions in $$$O(n \log n)$$$ time.

But there is a simple way to count parity of permutation, without directly counting number of inversions.

Theorem. Permutation can be represented as composition of 3-cycles if and only if it is even.

Proof. 3-cycle is even, so composition of 3-cycles must be even, so all that we need to do is proof, that for any even permutation exists such representation.

We will try to build our permutation from identical applying 3-cycles. On $$$i$$$-th iteration we assume, that first $$$i - 1$$$ elements of permutation are in place, and we will try to place $$$i$$$-th element. If $$$i$$$-th element is not in place, then now in current permutation it is on $$$j$$$-th place, $$$j > i$$$. Let's do cycle $$$n \to j \to i$$$, if $$$j \neq n$$$, and if $$$j = n$$$, do $$$n - 1 \to j \to i$$$, so we won't corrupt first $$$i - 1$$$ elements, and we will place $$$i$$$-th element.

So we can do $$$n - 2$$$ steps. After that there are two possible situations.

  1. $$$n - 1$$$-th and $$$n$$$-th elements are in place, this means that we represented our permutation as 3-cycles, so our permutation is even and we've found representation for it.

  2. They are not in place, they are swapped. Because on each step of algorithm permutation is even, and it differs from our permutation by one swap, thus our permutation is odd, so it can't be represented.

Implementation

So we've proven this theorem and got $$$O(n)$$$ algorithm with good constant, which can be useful in other problems involving parity of permutation.

  • Vote: I like it
  • +85
  • Vote: I do not like it

Comments Comments (18)
| Write comment?
»
3 years ago, # |
  Vote: I like it +50 Vote: I do not like it

Excuse me, in the contest, I checked if there are even number of (even vertices cycles) then the answer would be "YES" which is the same as the parity of the permutation is even. But how to prove that they are actually the same?

Thanks.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    Let's prove that the parity of $$$p \in S_n$$$ is the same as the parity of $$$n + cycles(p)$$$.

    Let's do induction over all $$$p \in S_n$$$ on the number of inversions. If $$$p$$$ has $$$0$$$ inversions (base case), the condition trivially holds. If not, choose an arbitrary inversion $$$(i, i+1)$$$ and swap those elements (this effectively decreases the number of inversions by $$$1$$$). The number of cycles will either increase or decrease (so their parity changes) and so does the parity. Therefore induction holds.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As was mentioned above parity of $$$f \circ g$$$ is sum of parities of $$$f$$$ and $$$g$$$.

    Note, that even length cycle is odd as permutation, and odd length cycle is even, because we can represent cycle length $$$L$$$ with $$$L - 1$$$ swaps. So if $$$f = C_1 \circ C_2 \circ \ldots \circ C_k$$$, and $$$m$$$ of them have even length, then $$$m$$$ of them are odd as permutations, so parity of $$$f$$$ is parity of $$$m$$$, that's exactly what you need.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And from this we can get, that parity of $$$f$$$ is $$$n + cycles(f)$$$. Indeed, if length of $$$C_i$$$ is $$$L_i$$$, then parity of $$$C_i$$$ is $$$L_i - 1$$$. Parity of $$$f$$$ is sum of parities over $$$C_i$$$, that is $$$(L_1 - 1) + (L_2 - 1) + \ldots + (L_k - 1)$$$, but sum of $$$L_i$$$ is $$$n$$$, so parity of $$$f$$$ is parity of $$$n - cycles(f)$$$, which is same as parity of $$$n + cycles(f)$$$

      → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Are there any other problems similar to the one discussed above?

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

hey man very intersting blog...are there any other resources where i can further read about thus stuff??

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I am not able to prove the lemma..any hints ??? thematdev

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 4   Vote: I like it +3 Vote: I do not like it

    Consider a permutation ________a_____b___________. Here we have to swap a and b. For now consider a > b (Similarly you can also prove for a<b).

    Lets define some terms

    Now observe carefully, if we swap a and b, the change in number of inversions of whole permutation will be only due to change in numbers of inversions of sub-array a_______b.

    By definition Inversion is pair (i,j) such that i<j, pi>pj. So before swaps number of inversion count of 'a' will be n1 = x2 + y2 + x3 + y3 + 1 and inversion count of 'b' will be m1 = x3

    After swap the values mentioned above will be n2 = x3 + y3 and m2 = x2 + x3 respectively.

    After swap inversion count of all numbers > a, present in part2 (z2) will increase by 1, coz 'a' which is less than them now will come after them. Similarly inversion count of all numbers > b, present in part2 (z2+y2) will decrease by 1, coz 'b' which is less than them now will come before them.

    so total change inversion count of whole permutation will be n2+m2 - (n1+m1) + z2 - (z2+y2) = -2y2 - 1, which is an odd number. So as change in inversion count is an odd number, after swapping two different numbers parity will definitely change

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Swap of two adjacent elements will change parity, because it either increases of decreases number of inversions by 1.

    Try to represent swap as odd number of adjacent swaps.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in the blog you have not made a relation between number of inversions and the cyclic representation of permutation..there must be some relation..You have proved the fact that permutation can be represented as composition of non-intersecting cycles..but how does it relate to the parity

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Check comments above, I and bicsi have proved, that parity of permutation $$$p$$$ length $$$n$$$ is $$$n + cycles(p)$$$ and also parity of number of even cycles.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

One thing to keep in mind is that, even though this algorithm is $$$O(n)$$$, it can be painfully slow for large values of $$$n$$$, for example, for $$$n=10^7$$$ it will usually take around $$$0.5$$$ seconds. I'm not aware of anything faster though maybe a Fenwick tree operating on single bits with XOR would be faster.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

very good blog,,but some examples would have helped

→ Reply
»
2 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Hello, I am having a bit of trouble seeing why a slightly easier approach was omitted (/ is wrong?)

With the above general idea in mind, can't we just represent our permutation as a number of transpositions and count the parity of this number?

example code:

int transpCount = 0;
for (int i = 1; i < n; i++)
  if(invp[i] != i) {
    transposition(i, invp[i]);
    transpCount++;
  }
if (transpCount % 2 == 0)
  ; // even permutation
else
  ; // odd permutation

my (AC) submission to 1591D using this idea.

*granted, the complexities (/ constants) of my solution and the one presented in the blog are virtually the same, but this seems more intuitive and I don't know why it wasn't presented.

Thank you! <3

→ Reply