Skiena’s TADM Problem 7-19

From Skiena’s Algorithm Design Manual
Problem 7-19

Use a random number generator (rng04) that generates numbers from {0, 1, 2, 3, 4} with equal probability to write a random number generator that generates numbers from 0 to 7 (rng07) with equal probability. What are expected number of calls to rng04 per call of rng07?

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

The basic idea is to represent the numbers 0..7 with three bits, where each bit is set randomly. To this end the rng04() is wrapped into a method rng03(), which trims its output to 0..3. Then, rng07() uses this output to set each of the three bits and return the random number in 0..7.

The code uses rng03() from the AlgoWiki.

Here is a Python 3 solution. Please leave comments if you find a mistake or an improvement.

#!/usr/bin/env python

import sys, random

# used for counting method calls. taken from
# http://stackoverflow.com/questions/1301735/counting-python-method-calls-within-another-method
def counted(fn):
    def wrapper(*args, **kwargs):
        wrapper.called+= 1
        return fn(*args, **kwargs)
    wrapper.called= 0
    wrapper.__name__= fn.__name__
    return wrapper

# RNG 0..4 (given)
@counted
def rng04():
    return random.randint(0,4)

# filtered call to rng04
# return 0..3
@counted
def rng03():
    while True:
        i = rng04()
        if i < 4:
            return i

# generate uniform numbers in 0..7
# use rng03 to generate representations of the 3 bits for
# numbers in the range 0..7
def rng07():
    b3 = rng03() % 2
    b2 = rng03() % 2
    b1 = rng03() % 2
    n = b3*4 + b2*2 + b1
    return n

if __name__ == "__main__":
    rands = []
    n = 100000
    for i in range(n):
        rands.append(rng07())
    for i in range(8):
        print (str(i) + "'s: " + str(rands.count(i)))

    print ("Called rng04() " + str(rng04.called) + " times")
    print ("rng04()/rng03() call ratio: " + str(rng04.called/rng03.called))
    print ("rng04()/rng07() call ratio: " + str(rng04.called/n))

    sys.exit()

Each call to rng07() calls rng03() to set each of the three bits, which in turn calls rng04() 5/4 times to obtain a number in 0..3. Hence, rng04() is called 5/4*3 = 3.75 times in average on each call to rng07(). The solution on the AlgoWiki requires about one call less, the solution on panictank requires more.

Skiena’s TADM Problem 7-15

From Skiena’s Algorithm Design Manual
Problem 7-15

Implement an efficient algorithm for listing all k-element subsets of n items.

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

This solution is based on Solution 7-1

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

#include <iostream>
#include <array>

#define N 5
#define K 3

// Comment 1: some function parameters are unused but kept
//            to provide consistency with Skiena's book

// By construction it is a solution if we reach the last element
bool is_a_solution (
    std::array<int, K>& arr, int k, int n
    ) {
    return k == n-1;
}

// processing = print it
void process_solution (
    std::array<int, K>& arr, int k, int n
    ) {
    for ( int i = 0; i != n; ++i )
        printf ("%i ", arr[i]);
    printf ( "\n" );
}

void construct_candidates (
    std::array<int, k="">& arr, int k, int n, std::array<int, n="">& cands, int& ncandidates
    ) {
    ncandidates = 0;

    if ( k == 0 ) {
        for ( int i=0; i != N; ++i )
            cands[ncandidates++] = i;
    } else {
    // all numbers greater than the currently greatest are candidates
        for ( int i = arr[k-1]+1; i != N; ++i )
            cands[ncandidates++] = i;
    }
}

void backtrack (
    std::array<int, K>& 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 );
        // pruning condition
        if ( ncandidates < K-k )
            return;

        for (int i=0; i<ncandidates; i++) {
            arr[k] = cands[i];
            backtrack ( arr, k, n );
        }
    }
}

int main () {

    std::array<int, K> arr = {0};
    int k = -1;

    backtrack ( arr, k, K );

    return 0;
}

Skiena’s TADM Problem 7-1

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.