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 *i*th 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 .

Mon Jun 2 23:33:50 EDT 1997