Permutations and arrangements

Permutations and arrangements are common concepts in many kinds of problems.

Definition

A bijection (that is, a one-to-one correspondence) from a set $X$ to itself, denoted by $\sigma$, is a permutation of $X$. If the set $X$ also has a total order, its permutation is also commonly called a (full) arrangement. This total order is called the natural order on the set.

If the size of a set $X$ is $n$, then the total number of permutations of $X$ is $n!$. In particular, $0!=1$: the empty set has exactly one permutation, namely the empty permutation.

Representations

There are several ways to represent a permutation. We use the following permutation as an example to discuss them.

Two-line notation

A permutation on the set $X=\{x_1,x_2,\cdots,x_n\}$ can be represented as

This means that permutation $\sigma$ maps $x_i$ to $x_{p_i}$. Of course, we need $X=\{x_{p_1},x_{p_2},\cdots,x_{p_n}\}$. In the two-line notation of a permutation, the order in which elements appear in the first row is not important; what matters is the correspondence between the two rows.

For example, the example above can be written in two-line notation as

and it can of course also be written as

One-line notation

In many cases, the set $X$ has a natural order. If the first row in two-line notation is assumed to be written in natural order and is omitted, the permutation can be represented as

This is closer to the concept of an arrangement in natural language. Therefore, “arrangement” is sometimes used to refer to this ordered tuple.

The example above can be written in one-line notation as

This one-line notation is often used to compare the sizes of different permutations.

Cycle notation

A permutation also has a more compact representation called its cycle notation. It represents a permutation as a product of pairwise disjoint cycles. The steps for writing a given permutation in cycle notation are described below.

Given a permutation $\sigma$, write it in cycle notation as follows:

1. If $X$ still contains an element that has not been written, write a left parenthesis and then write any such element;
2. If the most recently written element is $x$,
   • if $\sigma(x)$ has already been written, write a right parenthesis and return to step 1;
   • if $\sigma(x)$ has not yet been written, write $\sigma(x)$ and continue with step 2;
3. Stop when every element of $X$ has been written.

The elements inside each pair of parentheses form a cycle. The number of elements inside the parentheses is called the length of the corresponding cycle. In practice, cycles of length one are often omitted.

The example above can be written in cycle notation as

In the identity transformation, all cycles have length one, and it is common to write $(1)$ rather than omit them all.

Composition

Composition of permutations is composition of mappings. It is also commonly called multiplication of permutations.

Given two permutations

the product $\pi\circ\sigma$ is

In simple terms, first apply the mapping $\sigma$, then apply the mapping $\pi$. Note that in the two-line notation above, the order of the second row of the inner mapping $\sigma$ is the same as the order of the first row of the outer mapping $\pi$.

Because permutations $\sigma$ and $\pi$ are fundamentally mappings, $(\pi\circ\sigma)(x)=\pi(\sigma(x))$. The order of composition of permutations is from right to left. Multiplication of permutations is not commutative, so using the wrong order can produce an incorrect result.

The product of several consecutive copies of a permutation is called a power of the permutation, and binary exponentiation can accelerate its computation.

Inverse permutation

Because a permutation is a bijection, it always has an inverse permutation.

Given the permutation

its inverse is

In cycle notation, invert each cycle to obtain the inverse permutation. To invert a cycle, simply reverse the order in which its elements are written. For example, the inverse of the permutation $\sigma$ above has cycle notation

A permutation of $1\sim n$ and the sequence of the ranks of its elements are inverse permutations of each other.

Cycles

A cycle is itself a special permutation. The defining property of a cycle is that, starting from any point $x$ in the cycle, repeatedly applying the permutation $\sigma$ reaches any other point $y$ in the cycle. A cycle of length $k$ is also called a $k$-cycle (also written as a $k$-cycle). Repeatedly applying a $k$-cycle $k$ times gives the identity transformation: every element returns to its original position.

The cycle notation of a permutation can be viewed as expressing it as a product of these special permutations (cycles), so it can also be viewed as the cycle decomposition of the permutation. For every permutation, its decomposition into a product of cycles is unique up to the order of the cycles. Cycles can be viewed as the basic building blocks of a permutation.

The cycle decomposition of a permutation has a clear geometric meaning. If a permutation on a set $S$ is represented by treating each ordered pair $(x,\sigma(x))$ in it as an edge of a directed graph whose vertices are $S$, then the cycles are the loops in this graph. If permutation $\sigma$ decomposes into $m$ cycles, the corresponding directed graph has $m$ loops in total, including self-loops. These loops are naturally pairwise disjoint.

Fixed points

A $1$-cycle is a fixed point of a permutation. For a set $X$ and a permutation $\sigma$ on it, $X^\sigma$ usually denotes the set of fixed points of $\sigma$, namely $X^\sigma=\{x\in X:\sigma(x)=x\}$.

Transpositions

A $2$-cycle is also called a transposition. In other words, a transposition is a permutation that swaps exactly one pair of elements. Its cycle notation is $(x_ix_j)$, meaning that it swaps the positions of $x_i$ and $x_j$.

Every permutation can be written as a product of transpositions. This means that any ordering of elements can be restored to a specified sorted order by repeatedly swapping two elements. This is exactly what comparison-based sorting algorithms do.

Moreover, the correctness of bubble sort actually shows that every permutation can be written as a product of adjacent transpositions. An adjacent transposition is a transposition that swaps two adjacent elements.

Properties

Applications often require us to consider properties of an individual permutation.

Parity

The decomposition of a cycle into transpositions is not unique. For example,

However, when a permutation is decomposed into a sequence of transpositions, the parity of the number of transpositions required is fixed. The parity of the number of transpositions in a decomposition of a permutation is also called the parity of the permutation.

A permutation that can be decomposed into a product of an even number of transpositions is called an even permutation; one that can be decomposed into a product of an odd number is called an odd permutation. When $n\ge2$, the numbers of odd and even permutations of size $n$ are equal.

Sign

Based on the parity of a permutation, we can define its sign, denoted by $\operatorname{sgn}\sigma$. The sign of an even permutation is defined as $+1$, and that of an odd permutation as $-1$.

The sign of a product of permutations equals the product of their signs:

In other words, composing two permutations with the same parity gives an even permutation, while composing two permutations with different parities gives an odd permutation. From the viewpoint of decomposing into transpositions, this conclusion is immediate.

In particular, a single transposition necessarily changes the parity of a permutation. This also explains why, although the decomposition into transpositions is not unique, the parity of the required number of transpositions is fixed.

The sign of a permutation appears in the Leibniz expansion of the determinant.

Order of a permutation

The order of a permutation is the smallest positive integer $a$ satisfying the following condition: after applying the permutation repeatedly $a$ times, every element returns to its original position. That is,

On a finite set, every permutation has finite order. This means that, starting from an initial ordering, repeatedly scrambling a given sequence according to a fixed pattern will always restore the original arrangement in finite time.

Cycle type

Decompose a permutation of $n$ elements into cycles. The cycle type of the permutation is the multiset of the cycle lengths in the decomposition. These lengths form an integer partition of $n$. If cycles of length $k$ occur in the decomposition, with $\alpha_k$ of them, the cycle type is commonly written as

where the coefficients satisfy $\sum_{k=1}^nk\alpha_k=n$.

Given a cycle type, the number of distinct permutations is

If only the number of cycles $c(\sigma)$ in the permutation decomposition is given, the number of distinct permutations is the Stirling number of the first kind $\begin{bmatrix}n\\ k\end{bmatrix}$. The number of distinct cycle types for permutations of length $n$ is the partition number $p_n$.

The cycle type makes it easy to determine properties such as the order and parity of a permutation.

Because the order of a $k$-cycle is $k$ and distinct cycles are disjoint, the order of permutation $\sigma$ is

Likewise, because the parity of a $k$-cycle is opposite to the parity of $k$, the parity of permutation $\sigma$ is the parity of

Here, $c(\sigma)$ is the number of cycles, including $1$-cycles (fixed points).

Cycle types play an important role in Pólya enumeration.

Topics related to arrangements

If the set $X$ itself has a natural order, permutation $\sigma$ is commonly called an arrangement and represented in one-line notation as

Do not confuse this with a cycle.

Inversions

In an arrangement, if a larger number appears before a smaller number, the two numbers form an inversion. The comparison here uses the natural order.

The total number of inversions in an arrangement is called the inversion count of the permutation. The inversion count is the minimum number of adjacent transpositions needed to restore it to the sorted sequence. Therefore, the parity of the inversion count agrees with the parity of the corresponding permutation. This gives an equivalent definition of permutation parity.

Algorithms for computing inversion counts include merge sort and the binary indexed tree, both with time complexity $O(n\log n)$. Their explanations are given in the corresponding sections; reference implementations are provided here.

#include <iostream>
#include <vector>

// Merge sort and count inversions.
long long merge_sort(std::vector<int>& nums, int b, int e) {
  // Return 0 when length <= 1.
  if (e - b <= 1) return 0;
  long long res = 0;
  int m = (b + e) / 2;
  // Merge_sort two halves.
  res += merge_sort(nums, b, m);
  res += merge_sort(nums, m, e);
  // Temporary vector to store sorted array.
  std::vector<int> tmp(e - b);
  int i = b, j = m, k = 0;
  while (i < m && j < e) {
    if (nums[j] < nums[i]) {
      tmp[k] = nums[j++];
      // In this case, all elements in [i,m) are larger than element j.
      res += m - i;
    } else {
      tmp[k] = nums[i++];
    }
    ++k;
  }
  // Deal with remaining elements.
  for (; i < m; ++i, ++k) {
    tmp[k] = nums[i];
  }
  for (; j < e; ++j, ++k) {
    tmp[k] = nums[j];
  }
  // Copy back to original vector.
  for (i = b, k = 0; i < e; ++i, ++k) {
    nums[i] = tmp[k];
  }
  return res;
}

int main() {
  int n;
  std::cin >> n;
  std::vector<int> nums(n);
  for (int& num : nums) {
    std::cin >> num;
  }
  std::cout << merge_sort(nums, 0, n);
  return 0;
}

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>

// A simple BIT implementation.
class BIT {
  int n;
  std::vector<int> su;

 public:
  BIT(int n) : n(n), su(n + 1) {}

  // Add v to the x-th number.
  void add(int x, int v) {
    for (; x <= n; x += x & (-x)) {
      su[x] += v;
    }
  }

  // Get the cumulative sum till the x-th number.
  int query(int x) {
    int res = 0;
    for (; x; x &= x - 1) {
      res += su[x];
    }
    return res;
  }
};

// Count inversions.
long long solve(const std::vector<int>& nums) {
  // Discretization.
  std::vector<int> sorted(nums);
  std::sort(sorted.begin(), sorted.end());
  sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());
  std::unordered_map<int, int> ids;
  int m = sorted.size();
  for (int i = 0; i < m; ++i) {
    // Reverse the order.
    // Now a smaller id means a larger element.
    ids[sorted[i]] = m - i;
  }
  // Main part.
  BIT bit(m);
  long long res = 0;
  for (int num : nums) {
    int id = ids[num];
    // Get inversion pair (i,j) with j the current element.
    // Namely, count the number of elements larger than
    //     the current one but located before it.
    res += bit.query(id - 1);
    // Insert the current element to the BIT.
    bit.add(id, 1);
  }
  return res;
}

int main() {
  int n;
  std::cin >> n;
  std::vector<int> nums(n);
  for (int& num : nums) {
    std::cin >> num;
  }
  std::cout << solve(nums);
  return 0;
}

Order

Permutations can be compared by size. Since each one-line notation is a string, the order of permutations is the lexicographic order of these strings.

In the C++ STL library <algorithm>, prev_permutation and next_permutation can be used to find the previous and next permutations of the current one in lexicographic order.

Rank

List all permutations of $n$ elements in lexicographic order from smallest to largest. The position of a permutation in this sequence is its rank. This establishes a one-to-one correspondence between permutations and positive integers, and is often used for state compression in permutation problems.

In Chinese competitive programming, this rank is often called the “Cantor expansion” of a permutation, but that name is not standard. More precisely, the Cantor expansion of a permutation's rank corresponds to its Lehmer code.

From the example, the algorithm for finding the rank of a given permutation can be divided into two steps:

1. Convert the given permutation, of length $n$, into its Lehmer code, a sequence of length $n$ called $L_\sigma$, where the $i$-th entry is

   $$L_\sigma(i)=\#\{j>i:\sigma(j)<\sigma(i)\},$$

   that is, the number of elements after position $i$ in the permutation that are smaller than $\sigma(i)$. This is equal to the rank minus one of the given element among the unused elements.

2. Treat the Lehmer code as the Cantor expansion of a natural number, recover the original natural number, and add one. In other words, the final rank is

   $$\operatorname{rank}\sigma=1+L_\sigma(1)(n-1)!+L_\sigma(2)(n-2)!+\cdots+L_\sigma(n)0!.$$

To solve the inverse problem—given a rank, find the corresponding permutation—simply perform the above process in reverse. The sum of the digits in the Lehmer code obtained during this process is the inversion count of the permutation.

When implementing this, the key is to quickly compute the rank of a given element among the unused elements (when finding a rank) and the element with a given rank among the unused elements (when finding a permutation). Both can be maintained with data structures such as a binary indexed tree or a segment tree. Both forward and reverse operations take $O(n\log n)$ time.

#include <iostream>
#include <vector>

// A simple BIT implementation.
class BIT {
  int n;
  std::vector<int> su;

 public:
  BIT(int n) : n(n), su(n + 1) {}

  // Add v to the x-th number.
  void add(int x, int v) {
    for (; x <= n; x += x & (-x)) {
      su[x] += v;
    }
  }

  // Get the cumulative sum till the x-th number.
  int query(int x) {
    int res = 0;
    for (; x; x &= x - 1) {
      res += su[x];
    }
    return res;
  }
};

// Get the rank of a permutation of 1~n.
long long find_rank(const std::vector<int>& nums) {
  int n = nums.size();
  BIT bit(n);
  long long fac = 1;
  long long res = 0;
  // Reverse iteration.
  for (int i = n - 1; i >= 0; --i) {
    // Count the number of elements smaller than the current one.
    res += bit.query(nums[i] - 1) * fac;
    // Insert the current element into the BIT.
    bit.add(nums[i], 1);
    // Update the factorial.
    fac *= n - i;
  }
  return res + 1;
}

int main() {
  int n;
  std::cin >> n;
  std::vector<int> nums(n);
  for (int& num : nums) {
    std::cin >> num;
  }
  std::cout << find_rank(nums);
  return 0;
}

#include <cmath>
#include <iostream>
#include <vector>

// A simple BIT implementation.
class BIT {
  int n;
  std::vector<int> su;

 public:
  BIT(int n) : n(n), su(n + 1) {}

  // Fill the BIT with one.
  void fill() {
    for (int x = 1; x <= n; ++x) {
      su[x] += x & (-x);
    }
  }

  // Add v to the x-th number.
  void add(int x, int v) {
    for (; x <= n; x += x & (-x)) {
      su[x] += v;
    }
  }

  // Get the k-th smallest element.
  int find_kth(int k) {
    int ps = 0, x = 0;
    for (int i = log2(n); i >= 0; --i) {
      x += 1 << i;
      if (x >= n || ps + su[x] >= k) {
        x -= 1 << i;
      } else {
        ps += su[x];
      }
    }
    return x + 1;
  }
};

// Find the k-th permutation of 1~n.
std::vector<int> find_permutation(int n, long long k) {
  --k;
  // Expand rank to Lehmer code.
  std::vector<int> lehmer(n);
  for (int i = 1; i <= n; ++i) {
    lehmer[n - i] = k % i;
    k /= i;
  }
  BIT bit(n);
  // Set all values in BIT to one.
  bit.fill();
  std::vector<int> res(n);
  for (int i = 0; i < n; ++i) {
    // Find the lehmer[i]-th smallest unused element.
    res[i] = bit.find_kth(lehmer[i] + 1);
    // Remove it from the BIT.
    bit.add(res[i], -1);
  }
  return res;
}

int main() {
  int n;
  long long k;
  std::cin >> n >> k;
  auto res = find_permutation(n, k);
  for (int num : res) {
    std::cout << num << ' ';
  }
  return 0;
}

References and notes

• Permutation - Wikipedia
• Lehmer code - Wikipedia
• Factorial number system - Wikipedia