Программа для поиска анаграмм С++

Ваша задача решается через permutation входного слова и пересечение 2-х контейнеров

в примере вместо чтения файлов просто вектор строк)

Вот алгоритм :

1) Входное слово очищается от пробелов(если они есть), далее все это permutation с добавлением пробела после каждого цикла permutation и пишется в unordered_set (пробел добавляется для получения всех разбиений слова прим. вх: ap вых: ap, pa, a p, p a) тут надо не забыть сделать trim + multispace на входные данные если это надо)

2) Дампите словарь в контейнер и находите пересечение permutation и словаря

UPD: у функции AllWordPermutation есть 2 режима работы связанной с генерацией данных.

в 1 режиме (флаг true) - будут генерироваться только отдельные слова по типу вх. ab ; исх a, ab, b, ba 2 режим не разбивает строки на лексемы и на выходе будут "a b" "ba" "ab"

UPD2: AllWordPermutation2 теперь реализует метод Heap'a

#include <iostream>
#include <vector>
#include <algorithm>
#include <vector>
#include <iterator>
#include <unordered_set>
#include <string>
#include <sstream>

void StringToLower(std::string& line) {
    std::transform(std::begin(line), std::end(line), std::begin(line),
                   [](unsigned char c){ return std::tolower(c); });
}

std::string trim(std::string str, bool multi_space = true) {
    auto trim_left_it{std::find_if(std::begin(str), std::end(str), [](char ch){return !std::isspace(ch);})};
    str.erase(std::begin(str), trim_left_it);
    auto trim_right_it{std::find_if(std::rbegin(str), std::rend(str), [](char ch){return !std::isspace(ch);})};
    str.erase(trim_right_it.base(), std::end(str));
    if (multi_space) {
        std::string res;
        std::unique_copy(std::begin(str), std::end(str),
                        std::back_insert_iterator<std::string>(res),
                        [](char a,char b){ return isspace(a) && isspace(b);});
        return res;
    }
    return str;
}

std::vector<std::string> split_str(const std::string& str) {
    std::vector<std::string> tokens;
    std::size_t prev = 0, pos = 0;
    do {
        pos = str.find(' ', prev);
        if (pos == std::string::npos) {
            pos = str.length();
        }
        std::string token = str.substr(prev, pos-prev);
        if (!token.empty()) {
            tokens.push_back(token);
        }
        prev = pos + 1;
    } while (pos < str.length() && prev < str.length());
    return tokens;
}

std::vector<std::string> AllWordPermutation(std::string word, bool separate_all = true) {
    word.erase(std::remove(std::begin(word), std::end(word), ' '), std::end(word));
    std::sort(std::begin(word), std::end(word));
    std::unordered_set<std::string> perm_data_set;
    if (!separate_all) {
        word.append(word.length() - 1, ' ');
        do {
            perm_data_set.insert(trim(word));
        } while (std::next_permutation(std::begin(word), std::end(word)));
    } else {
        for (auto ch : word) {
            perm_data_set.insert(std::string{ch});
        }
        word.append(word.length() - 2, ' ');
        std::string tmp_word;
        do {
            auto splited{split_str(trim(word))};
            for (auto sub_word : splited) {
                perm_data_set.insert(trim(sub_word));
            }
        } while (std::next_permutation(std::begin(word), std::end(word)));
    }
    std::vector<std::string> ret{std::begin(perm_data_set), std::end(perm_data_set)};
    std::sort(std::begin(ret), std::end(ret));
    return ret;
}
std::vector<std::string> AllWordPermutation2(std::string s) {
    s.erase(std::remove(std::begin(s), std::end(s), ' '), std::end(s));
    std::sort(std::begin(s), std::end(s));
    std::unordered_set<std::string> perm_data_set;
    for (auto ch : s) {
            perm_data_set.insert(std::string{ch});
    }
    s.append(s.length() - 2, ' ');
    std::function<void(char*, std::size_t, std::size_t, std::unordered_set<std::string>&)> heapPermutation;
    auto ins{[&](char* a, std::size_t n, std::unordered_set<std::string>& perm_data_set)
                    {
                        auto splited{split_str(trim(std::string{a, a + n}))};
                        for (auto sub_word : splited) {
                             perm_data_set.insert(trim(sub_word));
                        }
                    }};
    heapPermutation = [&] (char* a,std::size_t size, std::size_t n, std::unordered_set<std::string>& perm_data_set) {
                                if (size == 1) {
                                    ins(a, n, perm_data_set);
                                    return; 
                                } 
                                for (std::size_t i{0}; i < size; ++i) { 
                                    heapPermutation(a, size-1, n, perm_data_set);
                                    if ((size % 2) == 1) {
                                        std::swap(a[0], a[size-1]); 
                                    } else {
                                        std::swap(a[i], a[size-1]); 
                                    }
                                } 
                           };
    heapPermutation(&s[0], s.length(), s.length(), perm_data_set);
    std::vector<std::string> ret{std::begin(perm_data_set), std::end(perm_data_set)};
    std::sort(std::begin(ret), std::end(ret));
    return ret;
}

std::vector<std::string> GetIntersection(std::vector<std::string>& perm_data, std::vector<std::string>& dict) {
    if (!std::is_sorted(std::begin(perm_data), std::end(perm_data))) {
        std::sort(std::begin(perm_data), std::end(perm_data));
    }
    if (!std::is_sorted(std::begin(dict), std::end(dict))) {
        std::sort(std::begin(dict), std::end(dict));
    }
    std::vector<std::string> intersection_ret;
    std::set_intersection(std::begin(perm_data), std::end(perm_data),
                          std::begin(dict), std::end(dict),
                          std::back_inserter(intersection_ret));
    return intersection_ret;
}

int main() {
    std::string word{"melon"};
    StringToLower(word);
    std::vector<std::string> dict{"sdas", "lemon", "dog", "stone", "olmen", "yeah", "hoho", "melon", "olnem", "no mel", "nom el", "l o n m e"};
    std::for_each(std::begin(dict), std::end(dict), StringToLower);
    std::cout << "Word : " << word << std::endl;
    std::cout << "Dict : ";
    std::copy(std::begin(dict), std::end(dict), std::ostream_iterator<std::string>{std::cout, " "});
    std::cout << std::endl;
    std::cout << std::endl;
    auto perm_data{AllWordPermutation(word, true)};
    std::cout << perm_data.size() << " combinations generated!" << std::endl;
    auto intersection_ret{GetIntersection(perm_data, dict)};
    std::copy(std::begin(intersection_ret), std::end(intersection_ret), std::ostream_iterator<std::string>{std::cout, "\t"});
    std::cout << std::endl << std::endl;

    auto perm_data2{AllWordPermutation2(word)};
    std::cout << perm_data2.size() << " combinations generated!" << std::endl;
    auto intersection_ret2{GetIntersection(perm_data2, dict)};
    std::copy(std::begin(intersection_ret2), std::end(intersection_ret2), std::ostream_iterator<std::string>{std::cout, "\t"});
    std::cout << std::endl;
    return 0;
}

На самом деле все намного легче:

разделяй и влавствуй

Нужно где то хранить заданное слово, чтобы проверять выполнение условия:

using std::string;
class Pred {
    const string s;
public:
    Pred(const string& basic)
        : s(basic) {}
    //если нет хоть одного символа из слова в нашей строке
    //то вернем ложь
    bool operator()(const string& str)
    {
        for (const char c : str) {
            if (s.find(c) == s.npos)
                return false;
        }
        return true;
    }
};

Теперь нужно читать из файла слова в какой нибудь контейнер, а потом сортировать согласно требованию:

auto get_set(std::istream& file, const string& str)
{  
    std::vector<string> v;
    using Input = std::istream_iterator<string>;
    std::copy_if(Input(file), Input(), std::back_inserter(v), Pred(str));
    std::sort(v.begin(), v.end(), [](const string& s1, const string& s2)
        { return s1.size() < s2.size(); });
    return v;
}

Программа будет простая. Например:

auto seq = get_set(input_file, "some_string");
for (auto& s : seq)
    cout << s << '\n';