Next: Constructing All Paths in Up: Backtracking Previous: Constructing All Subsets

Constructing All Permutations

To design a suitable state space for representing permutations, we start by counting them. There are n distinct choices for the value of the first element of a permutation of . Once we have fixed this value of , there are n-1 candidates remaining for the second position, since we can have any value except (repetitions are forbidden). Repeating this argument yields a total of distinct permutations.

This counting argument suggests a suitable representation. To construct all n! permutations, set up an array/vector A of n cells. The set of candidates for the ith position will be the set of elements that have not appeared in the (i-1) elements of the partial solution, corresponding to the first i-1 elements of the permutation. To use the notation of the general backtrack algorithm, . The vector A contains a full solution whenever k = n+1. This representation generates the permutations of in the following order:

The problem of generating permutations is more thoroughly discussed in Section .

Algorithms
Mon Jun 2 23:33:50 EDT 1997