Algorithms

Permutations

Order matters. Every arrangement counts.

01 — The Concept

What is a Permutation?

A permutation is an ordered arrangement of all or part of a set of objects. Unlike combinations, the specific order is crucial — ABC and BAC are two different permutations.

P(n, r) = n! / (n−r)!

n = total number of items
r = items chosen at a time
! = factorial

When you allow different lengths — picking 1, 2, or all characters — the total count becomes a sum:

Σ n!/(n−r)! for r = 1 … n

02 — Types

Three Kinds

TYPE 01

Distinct

All items are unique. The standard case — no repeats allowed.

TYPE 02

Repeating

Elements can be reused. "AAB" and "ABA" are both valid.

TYPE 03

Cyclic

Circular arrangements where rotations of the same order are identical.

03 — Example

Let's Try "ABC"

For a 3-character string with variable length, here are all 15 permutations. Hover to highlight. Color = length.

Input → "ABC" | All permutations (r=1,2,3)

A B C AB AC BA BC CA CB ABC ACB BAC BCA CAB CBA

Total: 15 permutations · 3 of length 1 · 6 of length 2 · 6 of length 3

04 — The Intuition

How to Think About It

Before writing a single line of code, build the mental model:

I can pick just one character at a time.

I can pick any two characters in any order.

I can pick all characters.

For every character I choose, I have options from all remaining characters — so I recurse, tracking what I've already used.

Pseudocode

for every character:
    print current result     // every prefix is valid
    for every other character not yet used:
        add it, recurse, then remove it  // backtrack

The key insight: print before the loop so empty strings and prefixes are captured, then backtrack to explore every branch.

05 — Backtracking

Why Backtracking Matters

You're building permutations one character at a time. After fully exploring one path, you need to undo your last choice so you can try a different one. That undoing is backtracking.

These two lines are where it happens:

Java→result.deleteCharAt(result.length() - 1);remove the character we just added
→used.remove(i);un-mark it so siblings can use it

✗ Without backtrack

After exploring A→AB→ABC, your result still holds "ABC" and used still has {0,1,2} marked. You're stuck — no way to go back and try ACB, BAC, or any other branch.

✓ With backtrack

After ABC, you undo C, undo B, then try C next — giving ACB. Then undo A entirely and start from B. Every branch gets explored cleanly.

Here is a concrete trace through "ABC":

print ""

pick A → result="A" print "A"

pick B → result="AB" print "AB"

pick C → result="ABC" print "ABC"

↩ backtrack C → result="AB"

↩ backtrack B → result="A"

pick C → result="AC" print "AC"

pick B → result="ACB" print "ACB"

↩ backtrack B → result="AC"

↩ backtrack C → result="A"

↩ backtrack A → result=""

pick B → result="B" print "B" ... and so on

The used set prevents picking the same index twice on one path. Removing from it on backtrack makes that index available again for sibling branches — without this, you would never generate "BAC" because index 0 (A) would still appear used when starting from B.

06 — Implementation

Java Code

Java

import java.util.*;

class Main {
    public static void main(String[] args) {
        permutation("ABC", new StringBuilder(), new HashSet<>());
    }

    static void permutation(String in, StringBuilder result, Set<Integer> used) {
        System.out.println(result.toString());   // print every prefix

        for (int i = 0; i < in.length(); i++) {
            if (!used.contains(i)) {
                char c = in.charAt(i);
                used.add(i);                     // mark as used
                permutation(in, result.append(c), used);
                result.deleteCharAt(result.length() - 1);
                used.remove(i);                  // backtrack
            }
        }
    }
}

07 — Real World

Where It's Used

📊

Statistics

Probability calculations and sample space enumeration

🎵

Music

Twelve-tone technique and serial composition tone rows

💻

CS / Algorithms

Brute-force search, test generation, algorithm optimization