Permutation and Combination

Nov 16, 2025

Updated 1 day ago

2 min read

Permutation & Combination

Counting is one of the most fundamental skills in mathematics and computer science. Whether you're building a password validator, generating test cases, or solving a probability problem — two concepts sit at the heart of it all: Permutation and Combination. Let's break them down clearly, understand where they differ, and then dive into the elegant recursive algorithm that generates all permutations of a string.

1. Permutation — When Order Matters

A permutation is an arrangement of items where the order in which you place them matters.

Imagine you have three letters: A, B, C. How many ways can you arrange all three?

ABC, ACB, BAC, BCA, CAB, CBA → 6 arrangements
Order matters.
Selecting and arranging items.

Formula

P (n, r) = \frac{n !}{( n - r )!}

Where:

n = total number of items
r = number of items being arranged
n! = n factorial = n × (n−1) × (n−2) × ... × 1

Example: Arrange 3 letters from {A, B, C, D}

P (4, 3) = \frac{4 !}{( 4 - 3 )!} = \frac{24}{1} = 24

Think of permutations as filling numbered seats — seat 1, seat 2, seat 3 all matter.

2. Combination — When Order Does NOT Matter

A combination is a selection of items where order is irrelevant. You only care about which items are chosen, not how they are arranged.

Choosing a team of 3 from {A, B, C, D} — the team {A, B, C} is the same as {C, B, A}.

Order does not matter.
Only selecting items.

Formula

C (n, r) = \frac{n !}{r ! ( n - r )!}

Example: Choose 3 from {A, B, C, D}

C (4, 3) = \frac{4 !}{3 ! \cdot 1 !} = \frac{24}{6} = 4

Think of combinations as picking a committee — it doesn't matter who was picked first.

3. The Relationship Between P and C

Permutation and Combination are deeply related. Every combination can generate multiple permutations by rearranging its selected elements:

P (n, r) = C (n, r) \cdot r!

Or equivalently:

C (n, r) = \frac{P ( n , r )}{r !}

Intuition: When you go from a combination to a permutation, you multiply by r!r! r! — the number of ways to arrange the rr r chosen items. Going the other way, you divide out all those redundant orderings.

4. Quick Comparison Table

Feature	Permutation	Combination
Order matters?	Yes	No
Formula	n! / (n−r)!	n! / r!(n−r)!
ABC ≠ CBA?	True	False (same set)
Use case	Passwords, rankings	Teams, selections
P vs C for same n,r	Always ≥ C	Always ≤ P

5. The Recursive Permutation Algorithm

cpp

void permute(char arr[], int i, int n) {
    if(i == n){
        print(arr);
        return;
    }

    for (int j = i; j<= n; j++) {
        swap(arr[i], arr[j]);
        permute(arr, i + 1, n);
        swap(arr[i], arr[j]); // backtrack undo the swap
    }
}