**Problem 7-1**

A derangement is a permutation \(p\) of \(\{1,…,n\}\) such that no item is in its proper position, i.e. \(p \not= i\,\, \forall\,\, 1 \le i \le n\). Write an efficient backtracking program with pruning that constructs all the derangements of n items.

**Solution**

(no guarantee that the solution is good or even correct)

Compile with -std=c++11 and please leave comments if you find a mistake or an improvement.

#include <iostream> #include <array> #define N 10 // Comment 1: some function parameters are unused but kept // to provide consistency with Skiena's book // Comment 2: there is no pruning because the candidate lists // are constructed to contain only possible numbers // By construction it is a solution if we reach the last element bool is_a_solution ( std::array<int, N>& arr, int k, int n ) { return k == n-1; } // processing = print it void process_solution ( std::array<int, N>& arr, int k, int n ) { for ( int i = 0; i != n; ++i ) printf ("%i ", arr[i]); printf ( "\n" ); } void construct_candidates ( std::array<int, N>& arr, int k, int n, std::array<int, N>& cands, int& ncandidates ) { ncandidates = 0; // generate a full list of candidates int candlist[N]; for ( int i = 0; i != n; ++i ) candlist[i] = i; // remove those that are in the array already and the one in position k for ( int i = 0; i != k; ++i ) candlist[arr[i]] = -1; candlist[k] = -1; // the rest are candidates for ( int i = 0; i != n; ++i ) if ( candlist[i] != -1 ) cands[ncandidates++] = candlist[i]; } void backtrack ( std::array<int, N>& arr, int k, int n ) { std::array<int, N> cands = {0}; int ncandidates; if ( is_a_solution ( arr, k, n )) process_solution ( arr, k, n ); else { k = k+1; construct_candidates ( arr, k, n, cands, ncandidates ); for (int i=0; i<ncandidates; i++) { arr[k] = cands[i]; backtrack ( arr, k, n ); } } } int main () { std::array<int, N> arr = {-1}; int k = -1; backtrack ( arr, k, N ); return 0; }