Beam search implemented in C++11

beam_search.cc

// To build this program: g++ -std=c++11 beam_search.cc -o bs
//
#include <iostream>
#include <set>
#include <string>
#include <functional>
#include <map>
#include <utility>
#include <algorithm>

typedef std::string Alphabet;
typedef std::string Sequence; // for operator +, or we can use vector and define +.
typedef std::function<double(const Sequence&, double, char)> ScoreFn;
typedef std::multimap<double, Sequence> Boundary;

void print_boundary(const Boundary& boundary) {
  for (auto& t : boundary) {
    std::cout << t.first << " : " << t.second << "\n";
  }
}

void beam_search(const Alphabet& alphabet, ScoreFn score_fn, int T, size_t K) {
  Boundary boundary = { {0.0, ""} };

  for (int t = 0; t < T; t++) {
    Boundary new_boundary;

    for (auto& beam : boundary) {
      for (auto& letter : alphabet) {
	new_boundary.insert(make_pair(score_fn(beam.second, beam.first, letter),
				      beam.second + letter));
	  
      }
    }

    size_t k = std::min(K, new_boundary.size());
    boundary.clear();
    std::copy_n(new_boundary.begin(), k, std::inserter(boundary, boundary.begin()));
    print_boundary(boundary);
    std::cout << "\n";
  }
}

int main() {
  const Alphabet alphabet { 'a', 'z' };
  beam_search(alphabet,
	      [](const Sequence& seq, double weight, char letter) {
		return weight - static_cast<double>(letter);
	      },
	      4, 5);
}

It outputs:

$ g++ -std=c++11 bs.cc -o bs && ./bs
-122 : z
-97 : a

-244 : zz
-219 : za
-219 : az
-194 : aa

-366 : zzz
-341 : zza
-341 : zaz
-341 : azz
-316 : zaa

-488 : zzzz
-463 : zzza
-463 : zzaz
-463 : zazz
-463 : azzz