Skip to content

Latest commit

 

History

History
143 lines (93 loc) · 5.1 KB

permutation.md

File metadata and controls

143 lines (93 loc) · 5.1 KB

Permutations and Transpositions

Ref: https://codeforces.com/blog/entry/111187 (nor's blog)

Def: Permutation is a shuffle of range [1, N], in other word, permutation is a bijection on a set.

Inversion

Inversion is pair (i,j), i < j such that p[i] > p[j]. Inversion count of an array if the number of inversion in the array.

  • Adjacent swaps changes inversion count by 1. (trivial)
  • Non-adjacent swaps flips inversion count. (Proof: follows from cycle decomposition)

Cycle Decomposition

Every permutation is composed of cycles. Proof?

  • Consider a permutation [p1, p2, p3, ...., pN].
  • ith element goes to p[i] th position, p[i]th element goes to p[p[i]] position and so on!
  • Positions are limited so some kth position will repeat in the traversal. Let say it is not the start position.
  • By bijection, p^-1[a[k]] = p^-1[a[l]]. so a[k-1] = a[l-1], which contradicts the minimality.
  • So it forms a cycle.

Each permutation can be decomposed into disjoint cycles. E.g. [23154] = (123)(45)

  • Permutations form functional graphs. Every vertex has a out degree.
  • How to find the vertex v which is reached if you travel k times along the permutation graph from a vertex u?
  • Use Binary Lifting!

Problems:

  1. CSES Planet Queries I https://cses.fi/problemset/task/1750
  2. CSES Planet Queries II https://cses.fi/problemset/task/1160

Transpositions

  • Swaps in an array are called transpositions.
  • Swapping two elements in a cycle, breaks the cycle into two.
  • Swapping two elements from two different cycles merge the cycles.

Problem: Lucky Permutation https://codeforces.com/contest/1768/problem/D

Hint: Cycle decomposition!

Number of transpositions required to sort an array?

  • Each transposition can reduce a cycle size by 1. Finally it has n cycles. So minimum number of transpositions is n - cycles.

Parity of Transpositions

  • Transpositions flip parity.
  • All even sized cycles have odd parity.
  • All odd sized cycles have even parity.
  • Parity add up module 2 over composition of cycles.
  • Parity of permutation is odd if number of even sized cycles is odd.
  • Parity of permutation is even if number of even sized cycles is even.
  • Odd number of swaps means odd parity of permutations.

Inversion

  • Inverse of a cycle [c1 c2 c3 ... ck] is its reverse [ck ... c3 c2 c1].
  • Inverse of a composition ab is b^-1 a^-1

Involution

  • a = c1 ...cm. Then, a^k = [c1^k, ..., cm^k].
  • id = a^2. So, c^k = id.
  • If k = 2, cycles can be 1 or 2 sized.
  • If k = 6 cycles can be 1, 2, 3, 6, factors of k!

Power of a permutation

  • kth power of a cycle corresponds to mapping to it kth next neighbour.
  • If the length of the cycle is c. c^k is composed of say g length cycles. (symmetry)
  • i + gk = i (mod c)
  • gk = 0 (mod c)
  • What is the least g? g = c/gcd(k,c)
  • Number of g length cycles = c/g = gcd(k,c).

Order of a permutation

  • Order of a permutation is defined as the least k such that a^k is identity.
  • A cycle of length L requires, a^L permutations to resolve into identity permutation.
  • If a permutation can be decomposed into cycles, minimum k to resolve it into identity permutation is LCM of all cycle lengths.

Square Root of a permutation

  • Define q^2 = p. Given p find q.
  • Decompose into cycles. cycles can multiple independently.
  • All odd cycles have a square root. Construct!
  • Two Even Cycles of same length can be combined to form a square.
  • In other words every square permutation has even cycles of a certain size in pairs.
  • Once you have the pairs you can form q1 * q2 = p'. p'^2 decompose into q1 and q2. Construct!

Square Root of a permutation : https://codeforces.com/contest/612/problem/E

Counting number of permutations with inversion count k

This problem can be solved with dynamic programming in N*K time.
Consider dp[N][K]. This denotes number of permutations with N distinct elements and K inversion count.

  • Transition : dp[N][K]
  • Sum { dp[N-1][1], dp[N-1][2], dp[N-1][3], dp[N-1][4], ..., dp[N-1][K-1] }
  • Sum { dp[N-1][J] } where K <= J + N-1 or J <= K - N + 1

Construction :

  • Consider a permutation P[1 2 3 4 ...N-1] with J inversion counts.
  • Now you want to achieve K inversion count where increase = K - J.
  • To the end of the array add an element which is smaller than K - J elements. Number could be fractional.
  • ReMap the array to P[1...N] according to the order of the elements.
  • New permutation is unique with K inversion count and can only be obtained from (N,J) uniquely.
	ll N, K; 
	cin >> N >> K;	
	
	dp[1][0] = 1;
	for (ll j=1;j<=K;j++) dp[1][j] = dp[1][j-1]; 
	for (ll i=2;i<=N;i++){
		for (ll inversions = 0; inversions <= K; inversions++){
			ll mn = max (0LL, inversions - i + 1); 
			ll mx = inversions;
			if (mn == 0) dp[i][inversions] = dp[i-1][mx];
			else dp[i][inversions] = (dp[i-1][mx] - dp[i-1][mn-1] + mod) % mod; 
			if (inversions) dp[i][inversions] = (mod + dp[i][inversions] + dp[i][inversions-1]) % mod;
		}
	}
	
	if (!K) cout << 1 << endl;
	else cout << (mod + dp[N][K] - dp[N][K-1]) % mod;