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 dictionary\n";
std::unordered_set<std::string> dictionary;
load_file(dictionary, "words");
std::cout << "Done\n";
//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 permutations\n";
if (permutations.size() > 500000)
{
std::cout << "making new\n";
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
Think about how you would go about this by hand - how do you check if two words are anagrams of each other?
e.g.: banana <-> aaannb
How would you solve this on a piece of paper? Would you create all 720 permutations and check if any one matches? Or is there an easier, more intuitive way?
So what makes a word an anagram of another word, i.e. what condition needs to be satisfied?
It's all about letter counts. If both words contain an equal amount of all letters, they're anagrams of each other.
e.g.:
banana -> 3x a, 2x n, 1x baaannb -> 3x a, 2x n, 1x bSo armed with this knowledge can you construct an algorithm that doesn't require iterating all possible permutations?
I'd only recommend to read this once you've tried to come up with your own optimized algorithm
You just need to build a lookup-table of letter-counts to dictionary words, e.g.:
1x a, 1x n -> ["an"]
3x a, 1x b, 2x n -> ["banana", "nanaba"]
1x a, 1x p, 1x r, 1x t -> ["part", "trap"]
... etc ...
then you can decompose your search word as well into letter counts, e.g. banana -> 3x a, 1x b, 2x n and search for the decomposition in your lookup table.
The result will be the list of words from your dictionary you can build with the given collection of letters - aka all possible anagrams for the given string.
aussuming some kind of structure named letter_counts that contains the letter composition the algorithm could look like:
std::vector<std::string> find_anagrams(std::vector<std::string> const& dictionary, std::string const& wordToCheck) {
// build a lookup map for letter composition -> word
std::unordered_map<letter_counts, std::vector<std::string>> compositionMap;
for(auto& str : dictionary)
compositionMap[letter_counts{str}].push_back(str);
// get all words that are anagrams of the given one
auto it = compositionMap.find(letter_counts{wordToCheck});
// no matches in dictionary
if(it == compositionMap.end())
return {};
// list of all anagrams
auto result = it->second;
// remove workToCheck from result if it is present
result.erase(std::remove_if(result.begin(), result.end(), [&wordToCheck](std::string const& str) { return str == wordToCheck; }), result.end());
return result;
}
This will run in O(n) time and has a space-complexity of O(n), with n being the number of words in the dictionary.
(It would be armortized O(1) time if you don't include the construction of the compositionMap as part of the algorithm)
In comparison to a permutation-based approach, that has O(n!) time complexity (or how i like to call it O(scary)).
Here's a full code example that only deals with letters a-z, but you can easily modify letter_counts to make it work with other characters as well:
#include <string_view>
#include <cctype>
#include <vector>
#include <string>
#include <unordered_map>
#include <iostream>
struct letter_counts {
static const int num_letters = 26;
int counts[num_letters];
explicit letter_counts(std::string_view str) : counts{0} {
for(char c : str) {
c = std::tolower(c);
if(c >= 'a' && c <= 'z')
counts[c - 'a']++;
}
}
};
bool operator==(letter_counts const& lhs, letter_counts const& rhs) {
for(int i = 0; i < letter_counts::num_letters; i++) {
if(lhs.counts[i] != rhs.counts[i]) return false;
}
return true;
}
template <class T>
inline void hash_combine(std::size_t& seed, const T& v)
{
std::hash<T> hasher;
seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}
namespace std {
template<>
struct hash<letter_counts> {
size_t operator()(const letter_counts& letterCounts) const
{
size_t result = 0;
auto hasher = std::hash<int>{};
for(int i : letterCounts.counts)
hash_combine(result, hasher(i));
return result;
}
};
}
std::vector<std::string> find_anagrams(std::vector<std::string> const& dictionary, std::string const& wordToCheck) {
// build a lookup map for letter composition -> word
std::unordered_map<letter_counts, std::vector<std::string>> compositionMap;
for(auto& str : dictionary)
compositionMap[letter_counts{str}].push_back(str);
// get all words that are anagrams of the given one
auto it = compositionMap.find(letter_counts{wordToCheck});
// no matches in dictionary
if(it == compositionMap.end())
return {};
// list of all anagrams
auto result = it->second;
// remove workToCheck from result if it is present
result.erase(std::remove_if(result.begin(), result.end(), [&wordToCheck](std::string const& str) { return str == wordToCheck; }), result.end());
return result;
}
int main() {
std::vector<std::string> dict = {
"banana",
"nanaba",
"foobar",
"bazinga"
};
std::string word = "aaannb";
for(auto& str : find_anagrams(dict, word)) {
std::cout << str << std::endl;
}
}