Permutations: Arrangements That Matter

June 2026 · 20 min read

A permutation is an ordered arrangement. Whenever order matters — seating people in a row, assigning ranks, or generating ordered sequences — you're counting permutations. This post covers every flavour you'll encounter in competitive programming, complete with implementation details.

What Are Permutations?

A permutation of a set S is a bijection from S to itself — equivalently, it's an ordered listing of all elements. The number of permutations of n distinct objects is n! (n factorial).

Factorials grow extremely fast. 20! > 2 × 10¹⁸, so for n ≥ 21 you'll always work modulo a prime in CP. Keep this in mind — brute-force enumeration is only feasible for n ≤ ~20.

// Precompute factorials mod p
const int MAXN = 200001;
const long long MOD = 1e9 + 7;
long long fact[MAXN];

void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++)
        fact[i] = fact[i-1] * i % MOD;
}

The P(n, r) Formula

When you choose r objects from n and arrange them in order (without replacement), the count is:

P(n, r) = n! / (n − r)! = n × (n−1) × … × (n−r+1)

This is sometimes written ⁿPᵣ. The derivation follows directly from the multiplication principle: n choices for the first slot, (n−1) for the second, …, (n−r+1) for the rth slot.

// Compute P(n, r) mod p using precomputed factorials and modular inverse
long long power(long long base, long long exp, long long mod) {
    long long result = 1; base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

long long inv(long long a, long long mod) {
    return power(a, mod - 2, mod);
}

long long P(int n, int r) {
    if (r > n) return 0;
    return fact[n] % MOD * inv(fact[n - r], MOD) % MOD;
}

Example: Assigning medals

10 athletes compete; gold, silver, and bronze are awarded. How many outcomes? P(10, 3) = 10 × 9 × 8 = 720.

Circular Permutations

When objects are arranged in a circle, rotations of the same arrangement are considered identical. Fix one element to break the symmetry; the remaining (n − 1) elements can be arranged in (n − 1)! ways.

Why (n−1)? Each circular arrangement corresponds to n different linear arrangements (one for each rotation). So circular = n! / n = (n−1)!.

// Seat n people around a circular table
// Answer: (n-1)! mod p
long long circularPerm(int n) {
    if (n <= 1) return 1;
    return fact[n - 1];
}

Permutations with Repetition

When some objects are identical, we divide out the redundant arrangements. If there are n objects total with n₁ of type 1, n₂ of type 2, …, nₖ of type k:

Multinomial: n! / (n₁! · n₂! · … · nₖ!)

Example. How many distinct arrangements of the letters in "MISSISSIPPI"? 11 letters total: M(1), I(4), S(4), P(2). Answer: 11! / (1! · 4! · 4! · 2!) = 34,650.

// Count distinct permutations of a string
long long countDistinctPerms(const string& s) {
    int freq[26] = {};
    for (char c : s) freq[c - 'a']++;
    int n = s.size();
    long long ans = fact[n];
    for (int i = 0; i < 26; i++)
        ans = ans % MOD * inv(fact[freq[i]], MOD) % MOD;
    return ans;
}

Restricted Permutations

Contest problems rarely ask for "plain" P(n,r). Constraints abound: certain elements must or must not be adjacent, specific positions are forbidden, etc.

Adjacent elements must be together

Treat the group as a single "super-element," count arrangements of the reduced set, then multiply by the internal arrangements of the group.

Forbidden positions (Derangements)

A derangement is a permutation where no element appears in its original position. The count D(n) satisfies:

D(n) = n! · Σₖ₌₀ⁿ (−1)ᵏ / k! ≈ n! / e

// Compute derangements mod p
long long derangements(int n) {
    // D(0)=1, D(1)=0, D(n) = (n-1)(D(n-1) + D(n-2))
    if (n == 0) return 1;
    if (n == 1) return 0;
    long long prev2 = 1, prev1 = 0, cur;
    for (int i = 2; i <= n; i++) {
        cur = (long long)(i - 1) % MOD * ((prev1 + prev2) % MOD) % MOD;
        prev2 = prev1;
        prev1 = cur;
    }
    return cur;
}

Implementation in C++

Here's a complete competitive-programming-ready snippet that handles all the permutation variants discussed above.

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 5;
long long fac[MAXN], ifac[MAXN];

long long power(long long b, long long e, long long m) {
    long long r = 1; b %= m;
    for (; e > 0; e >>= 1) {
        if (e & 1) r = r * b % m;
        b = b * b % m;
    }
    return r;
}

void init() {
    fac[0] = 1;
    for (int i = 1; i < MAXN; i++) fac[i] = fac[i-1] * i % MOD;
    ifac[MAXN-1] = power(fac[MAXN-1], MOD - 2, MOD);
    for (int i = MAXN - 2; i >= 0; i--) ifac[i] = ifac[i+1] * (i+1) % MOD;
}

long long perm(int n, int r) {
    if (r > n || r < 0) return 0;
    return fac[n] % MOD * ifac[n - r] % MOD;
}

long long multinomial(int n, vector<int>& groups) {
    long long ans = fac[n];
    for (int g : groups) ans = ans % MOD * ifac[g] % MOD;
    return ans;
}

long long derange(int n) {
    if (n == 0) return 1;
    if (n == 1) return 0;
    long long a = 1, b = 0, c;
    for (int i = 2; i <= n; i++) {
        c = (long long)(i - 1) % MOD * ((a + b) % MOD) % MOD;
        a = b; b = c;
    }
    return c;
}

int main() {
    init();
    int n, r;
    cin >> n >> r;
    cout << perm(n, r) << "\n";
    return 0;
}

Using next_permutation

For small n (≤ ~10), the STL next_permutation function is invaluable for brute-force solutions and stress tests:

// Enumerate all permutations of {1, 2, ..., n}
vector<int> v(n);
iota(v.begin(), v.end(), 1);
do {
    // process permutation v
} while (next_permutation(v.begin(), v.end()));

Practice Problems

1. CSES — Creating Strings. Generate all distinct permutations of a string in lexicographic order. Direct application of next_permutation with duplicate handling.
2. Codeforces 1547D — Co-growing Sequences. Think about which positions are "free" to permute.
3. Codeforces 1157C2 — Increasing Subsequence (Hard). Greedy + permutation structure.
4. CSES — Round Trip. Circular permutation ideas appear in cycle-finding on graphs.
5. Codeforces 340C — Arithmetic Progression. Count valid arrangements under constraints.
6. AtCoder ABC 199 E — Permutation. Bitmask DP to count permutations with prefix constraints — combines P(n,r) with DP over subsets.