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 
.