Permutations: Cycles, Next Permutation, Ranking and Inversions

A permutation of 0..n-1 is a rearrangement, best viewed as a function i -> p[i]. Interview questions about permutations revolve around a few concrete tools: cycle decomposition (minimum swaps, in-place rearrangement), the next permutation in lexicographic order, converting between a permutation and its rank, and counting inversions.

Intuition

Cycles. Start at i and keep following i -> p[i] -> p[p[i]] -> ...; since p is a bijection you must return to i. So every permutation splits into disjoint cycles, e.g. p = [2, 0, 1, 4, 3] has cycles (0 2 1) and (3 4). A cycle of length L can be fixed with L - 1 swaps and no fewer, so sorting by arbitrary swaps needs exactly n - (number of cycles) swaps.

Inverse and composition. The inverse q satisfies q[p[i]] = i ("where did element x go?"). Composing permutations is applying one after the other; it is associative but not commutative. A permutation and its inverse have the same cycle lengths.

Inversions and parity. An inversion is a pair i < j with p[i] > p[j]. The number of inversions equals the minimum number of adjacent swaps needed to sort, and its parity equals the parity of n - cycles. Every swap flips that parity, so it tells you whether an even or an odd number of swaps is needed; this is what decides puzzles like "can this sliding-tile position be solved".

Lexicographic order. Listing permutations like words in a dictionary, each permutation has a rank. The first element splits the list into n blocks of (n-1)!, the second element splits each block into blocks of (n-2)!, and so on: a mixed-radix (factorial) number system. That gives both directions, permutation to rank and rank to permutation.

When to use it in interviews / OAs

• "Minimum number of swaps to sort" or "to make two arrays equal" (cycles).
• "Rearrange in place with O(1) extra space according to an index array" (walk the cycles).
• "Next greater arrangement of the digits", "next permutation" (the suffix algorithm).
• "k-th permutation", "rank of a permutation" (factorial number system).
• "Count pairs out of order", "minimum adjacent swaps" (inversions with merge sort or a Fenwick tree).

Template: cycles

def cycles(p: list[int]) -> list[list[int]]:
    # p is a permutation of 0..n-1; follow i -> p[i] until the walk returns
    seen = [False] * len(p)
    out = []
    for start in range(len(p)):
        if not seen[start]:
            cyc, i = [], start
            while not seen[i]:
                seen[i] = True
                cyc.append(i)
                i = p[i]
            out.append(cyc)
    return out


def inverse(p: list[int]) -> list[int]:
    q = [0] * len(p)
    for i, x in enumerate(p):
        q[x] = i
    return q


def min_swaps_to_sort(arr: list[int]) -> int:
    # distinct values; a cycle of length L costs L - 1 swaps
    order = sorted(range(len(arr)), key=arr.__getitem__)  # order[k] = index of the k-th smallest
    return len(arr) - len(cycles(order))

order maps each sorted position to the index currently holding that value. It is the inverse of "index -> sorted position", and inverses have the same cycles, so either works.

Template: next permutation

Scan from the right for the first ascent a[i] < a[i+1]; everything after i is non-increasing, i.e. already the largest arrangement of that suffix. Swap a[i] with the rightmost element larger than it, then reverse the suffix to make it as small as possible.

def next_permutation(a: list) -> bool:
    # next lexicographic arrangement in place; returns False (leaving a sorted) after the last one
    i = len(a) - 2
    while i >= 0 and a[i] >= a[i + 1]:  # rightmost ascent a[i] < a[i + 1]
        i -= 1
    if i >= 0:
        j = len(a) - 1
        while a[j] <= a[i]:  # rightmost element larger than a[i]
            j -= 1
        a[i], a[j] = a[j], a[i]
    a[i + 1:] = reversed(a[i + 1:])  # the non-increasing suffix becomes its smallest arrangement
    return i >= 0

The non-strict comparisons make it correct with duplicate values too: it then walks through distinct arrangements only.

Template: rank and k-th permutation

The rank (1-based) is 1 + sum of L[i] * (n-1-i)!, where L[i] counts the later elements smaller than p[i]. A Fenwick tree over values gives each L[i] in O(log n). Going the other way, repeatedly divide k - 1 by (i-1)! to pick the next element from the remaining ones.

from math import factorial


def permutation_rank(p: list[int]) -> int:
    # 1-based lexicographic rank of a permutation of 1..n
    n = len(p)
    tree = [0] * (n + 1)  # Fenwick tree over values already seen to the right
    fact, rank = 1, 0
    for i in range(n - 1, -1, -1):
        smaller, v = 0, p[i] - 1
        while v > 0:  # how many later elements are smaller than p[i]
            smaller += tree[v]
            v -= v & -v
        v = p[i]
        while v <= n:
            tree[v] += 1
            v += v & -v
        rank += smaller * fact  # weight (n - 1 - i)!
        fact *= n - i
    return rank + 1


def kth_permutation(n: int, k: int) -> list[int]:
    # the k-th (1-based) permutation of 1..n in lexicographic order
    digits = list(range(1, n + 1))
    k -= 1
    out = []
    for i in range(n, 0, -1):
        idx, k = divmod(k, factorial(i - 1))  # which block of (i - 1)! permutations
        out.append(digits.pop(idx))
    return out

Template: counting inversions

Merge sort counts inversions while merging: when an element from the right half is placed before the remaining left elements, it forms an inversion with each of them.

def count_inversions(a: list[int]) -> int:
    arr = a[:]  # leave the caller's list untouched

    def sort(lo: int, hi: int) -> int:
        if hi - lo <= 1:
            return 0
        mid = (lo + hi) // 2
        count = sort(lo, mid) + sort(mid, hi)
        merged, i, j = [], lo, mid
        while i < mid and j < hi:
            if arr[i] <= arr[j]:
                merged.append(arr[i])
                i += 1
            else:
                merged.append(arr[j])
                j += 1
                count += mid - i  # arr[j] is smaller than every remaining left element
        merged += arr[i:mid] + arr[j:hi]
        arr[lo:hi] = merged
        return count

    return sort(0, len(arr))

Complexity

Cycle decomposition and inverse: O(n). Minimum swaps: O(n log n) because of the sort. Next permutation: O(n). Rank: O(n log n) with the Fenwick tree; k-th permutation: O(n^2) because of list.pop, fine for n up to a few thousand. Inversions: O(n log n).

Common pitfalls

• Arbitrary swaps vs adjacent swaps: the first is n - cycles, the second is the inversion count.
• Duplicates: cycle-based minimum swaps assumes distinct values; with duplicates the problem is harder (it becomes a cycle packing question).
• 0-based vs 1-based: ranks and k are usually 1-based in statements, the math is cleaner 0-based. Convert once at the boundary.
• Factorial overflow: 20! fits in a signed 64-bit integer, 21! does not. Ranks of long permutations need big integers or a modulus.
• Comparisons in next permutation: with > instead of >= (or < instead of <=) the scans misbehave on repeated values, treating equal neighbors as an ascent and running past the array.

Interview variations

• Next permutation, next greater number with the same digits (apply it to the digit list and check the 32-bit limit).
• Permutation sequence: k-th permutation; rank of a permutation: Lehmer code.
• Minimum swaps to sort, couples holding hands (cycles in a pairing graph), array nesting (longest cycle).
• Count inversions, reverse pairs (a[i] > 2 * a[j], same merge sort with a separate counting pass).
• Apply a permutation in place with O(1) extra space: rotate along each cycle, marking visited entries.
• Solvability of sliding puzzles: parity of inversions.