Permutations

Backtracking O(n · n!) O(n)

Generates every ordering of a set by fixing each position in turn and swapping, then undoing the swap.

building

[123]

recorded (0)

none yet

Elements: 1, 2, 3 · found 0 / 6

1/36

Fix position 0 = 1.

InvariantPositions 0..k-1 are fixed; the rest is a permutation of the values not used yet.

choosebacktrackrecorded

permutations.c

void permute(int a[], int n, int k) {
    if (k == n) {
        printPerm(a, n);
        return;
    }
    for (int i = k; i < n; i++) {
        swap(&a[k], &a[i]);
        permute(a, n, k + 1);
        swap(&a[k], &a[i]);   /* undo */
    }
}

How Permutations works

Fix the first position by swapping each candidate into it, recurse on the rest, then swap back. The undo keeps the array reusable across branches.

When to use it

Enumerating orderings: brute-force TSP, anagram generation, test-case shuffling.