13 Aug 2013 C++, next_permutation

Following up on the next_permutation from a couple of weeks ago word finder uses next_permutation to find words in character sequences. Uses the aspell C api to look up each permutation. Searching for 3,4,5 and 6 character words in a 6 character sequence takes about 200ms.

Using C++11 meant that I could use a nice lambda expression to process each permutation by passing the function object to the permute() function.

#pragma once

#include "word_accumulator.h"
#include "spell_checker.hpp"

void permute(vector<char> chars, std::function<void (const string&)> f) {
    do {
        string perm;
        for (auto x : chars)
            perm += x;

    } while (next_permutation(chars.begin(), chars.end()));

class word_finder {
    const char *seed;
    word_finder(const char *seed) : seed(seed) {

    template<typename T> vector<T> sorted_vector_of(const T *seed) {
        vector<T> y(seed, seed + strlen(seed));
        sort(y.begin(), y.end());
        return y;

    vector<string> find() {
        spell_checker checker;

        accumulator<string> accumulator;

        permute(sorted_vector_of(seed), [&](const string& w) {

            for (int i = 3; i <= w.size(); i++) {
                for (int j = 0; j <= w.size() - i; j++) {
                    string to_check(&w.c_str()[j], i);

                    accumulator.append_if(to_check, [&](const string& t) {
                        return checker.is_correct(t);

        return accumulator.sort_by([](const string& a, const string& b) {
            return b.length() == a.length() ? a < b : b.length() > a.length();


Graham Brooks Photo

This is a personal weblog. The opinions expressed here represent my own and not those of my employer (ThoughtWorks).

My thoughts and opinions change over time as I learn. This weblog is intended to provide a semi-permanent record of these thoughts and is for informational purposes only.

comments powered by Disqus