next up previous contents index CD CD Algorithms
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 tex2html_wrap_inline25690 . Once we have fixed this value of tex2html_wrap_inline25692 , there are n-1 candidates remaining for the second position, since we can have any value except tex2html_wrap_inline25694 (repetitions are forbidden). Repeating this argument yields a total of tex2html_wrap_inline25696 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, tex2html_wrap_inline25702 . The vector A contains a full solution whenever k = n+1. This representation generates the permutations of tex2html_wrap_inline25706 in the following order:


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

Mon Jun 2 23:33:50 EDT 1997