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;
}


# Create sorted 1D array from sorted 2D array

Problem:

Given a sorted 2D N x N array (where array[i][j] < array[i][j+1] and array[i][j] < array[i+1][j]), can you write a function that converts this to a sorted 1D array?

Solution:
A possible solution utilizes a propagating front separating the elements that have already been sorted into the 1D array from those that are still pending. The solution is $$\mathcal{O}(N)$$ in space because of the storage required for the front and $$\mathcal{O}(N^3)$$ in time as the insertion of each of the $$N^2$$ numbers requires a comparison of the N front values (at most).

The algorithm generalizes to sorting $$D$$-dimensional arrays, in which case the front has dimension $$D-1$$.

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

#include <iostream>
#include <limits>

using namespace std;
// typedef double arraytype;
typedef int arraytype;

#define N 4                                                                     // example with a 4x4 matrix

const arraytype mat[N][N] = {{1,2,4,5},{2,3,5,7},{4,6,12,13},{5,20,21,22}};     // sorted 2D array

int main () {

arraytype arr[N*N] = {0};                                                   // initialize the array to zero
unsigned int front[N] = {0};                                                // use a front that contains the first number to consider for each column, i.e.,
// the first number in each column that has not be sorted in the 1D array yet

for ( unsigned int n = 0; n != N*N; ++n ) {                                 // loop the 1D array
arraytype m = numeric_limits<arraytype>::max();                         // init smallest element found to max
unsigned int f = 0;                                                     // variable for updating the front in one column
for ( unsigned int col = 0; col != N; ++col ) {                         // walk the 2D array by columns
if ( front[col] == N ) continue;                                    // if the front hits row N in column col go to next column
if ( (col > 0) && (front[col] == 0) && (front[col-1] == 0) ) break; // optimization: stop the current column iteration if the front in column col and col-1 is at row 0 (and col > 0)
if ( m > mat[front[col]][col] ) {                                   // check 2D array for value smaller than m
m = mat[front[col]][col];                                       // update m
f = col;                                                        // set f for updating front but don't update front yet because another smaller value might be found
}
}
arr[n] = m;                                                             // set value in 1D array
front[f]++;                                                             // update front
}

for ( auto& i : arr )                                                       // print sorted 1D array
cout << i << " ";
cout << endl;

return 0;
}


Solutions with complexity of $$\mathcal{O}(N^2)\log(N)$$ are achieved by maintaining the front values in a priority queue. This is the same as the merge step of mergesort.

Simply adding all values of the 2D array into a min heap and extracting them of the top is also $$\mathcal{O}(N^2)\log(N)$$ (as $$\mathcal{O}(N^2)\log(N^2) = \mathcal{O}(N^2)2\log(N) = \mathcal{O}(N^2)\log(N)$$). Adding the values to the heap following diagonals from the largest number (bottom right) to the smallest number (top left) will reduce the bubble down time.