enumerating all permutations

Sometimes the answer is not which items but in what order. Seating n guests around a table, scheduling n jobs on one machine, deciding the route through n cities — each is a choice of ordering, and the set of all orderings of n distinct items is the set of permutations. There are exactly n! of them: n choices for what goes first, then n-1 for second, n-2 for third, and so on down to 1.

A natural way to generate them all is recursion that fixes positions one at a time. To list the permutations of a set, pick each available element in turn to be the first, then recursively list all permutations of the remaining elements, and prepend your choice. The base case is the empty set, whose only permutation is the empty sequence. This visits each permutation exactly once: at depth 1 you branch n ways, at depth 2 the remaining n-1 ways, and the product n * (n-1) * ... * 1 = n! is precisely the number of leaves, so nothing is missed or repeated. Many languages also offer a next-permutation routine that, given one ordering, computes the next in lexicographic order in place, so you can sweep all n! orderings with a simple loop.

Permutation enumeration is the brute force behind the traveling salesman problem, optimal job sequencing, and assignment problems before smarter methods are applied. Its cost is brutal: n! grows faster than any exponential 2^n, so even n = 13 gives over six billion orderings and n = 20 is utterly hopeless. This steepness is exactly why permutation problems are a showcase for branch and bound, dynamic programming over subsets (the Held-Karp method for TSP runs in O(2^n n^2), far better than n!), and heuristics.