is there any way to speed up the permuation creation for an anagramsolver?

  anagram, c++, permutation

I’m currently trying to make a very fast anagram solver, and right now it’s bottlenecked by the creation of the permutations. is there another way to do the whole program or to optimize the permutation creation?
here’s my code:

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <unordered_set>
#include <vector>
#include <boost/asio/thread_pool.hpp>
#include <boost/asio/post.hpp>



void get_permutations(std::string s, std::vector<std::string> &permutations)
{
    std::sort(s.begin(), s.end());
    do
    {
        permutations.push_back(s);
    } while (std::next_permutation(s.begin(), s.end()));
}


void load_file(std::unordered_set<std::string> &dictionary, std::string filename)
{
    std::ifstream words(filename);
    std::string element;
    while (words >> element)
    {
        std::transform(element.begin(), element.end(), element.begin(), ::tolower);
        dictionary.insert(element);
    }
}

void print_valid(const std::unordered_set<std::string>& dictionary, const std::vector<std::string>::const_iterator start, const std::vector<std::string>::const_iterator stop)
{
    for (auto iter = start; iter != stop; iter++)
    {

        if (dictionary.contains(*iter) == true)
        {
            std::cout << *iter << "n";
        }
    }
}

int main()
{
    const std::string s = "asdfghjklq";
    std::vector<std::string> permutations;
    boost::asio::thread_pool pool(2);
    std::cout << "Loading english dictionaryn";
    std::unordered_set<std::string> dictionary;
    load_file(dictionary, "words");
    std::cout << "Donen";

    //std::cout << "Enter the anagram: ";
    //getline(std::cin, s);

    clock_t start = clock();


    get_permutations(s, permutations);
    //std::cout << permutations.size() << std::endl;

    std::cout << "finished permutationsn";

    
    if (permutations.size() > 500000)
    {
        std::cout << "making newn";
        for (size_t pos = 0; pos < permutations.size(); pos += (permutations.size() / 3))
        {
            boost::asio::post(pool, [&dictionary, &permutations, pos] { print_valid(dictionary, (permutations.begin() + pos), (permutations.begin() + pos + (permutations.size() /3) ) ); });
        }
        pool.join();
    } 
    else
    {
        print_valid(dictionary, permutations.begin(), permutations.end());
    }

    

    clock_t finish = clock();
    double time_elapsed = (finish - start) / static_cast<double>(CLOCKS_PER_SEC);
    std::cout << time_elapsed << "n";
    std::cout << permutations.size() << std::endl;

    return 0;
}

the creation of permutations is in get_permutations
the thread pooling was something to test for very large sets of permutations

Source: Windows Questions C++

LEAVE A COMMENT