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

Leave a Reply