From Skiena’s Algorithm Design Manual
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;
}


One thought on “Skiena’s TADM Problem 7-1”

1. Pingback: Skiena's TADM Problem 7-1