#include <algorithm>
#include <Windows.h>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace  std;

bool is_anagram(string first, string second)
{
    sort(first.begin(), first.end());
    sort(second.begin(), second.end());

    return first == second;
}
void func(vector<vector<string>>& correct, vector<string>& result, vector<string>& variant, size_t next_id, size_t& n_words)
{
    for (size_t i = next_id; i < correct.size(); i++)
    {
        string tmp;
        for (size_t j = 0; j < correct[i].size(); j++)
        {
            tmp = correct[i][j];
            vector<string> copy = variant;
            copy.push_back(tmp);
            func(correct, result, copy, i + 1, n_words);
        }
    }
    if (variant.size() == n_words)
    {
        string tmp;
        for (size_t i = 0; i < variant.size(); i++)
            tmp += variant[i] + " ";
        bool is_unique = true;
        for (size_t i = 0; i < result.size(); i++)
            if (result[i] == tmp)
            {
                is_unique = false;
                break;
            }

        if (is_unique)
            result.push_back(tmp);
    }
}

void f(vector<vector<string>>& correct)
{
    vector<string> variant, result;
    size_t size = correct.size();
    vector< size_t > permutation;

    for (size_t i = 0; i < size; i++)
        permutation.push_back(i);

    do
    {
        for (size_t i = 0; i < permutation.size(); i++)
        {
            swap(correct[i], correct[permutation[i]]);
            func(correct, result, variant, 0, size);
        }
    } while (std::next_permutation(permutation.begin(), permutation.end()));

    sort(result.begin(), result.end());
    for (size_t i = 0; i < result.size(); i++)
        cout << result[i] << endl;
}

int main()
{
    SetConsoleOutputCP(1251);
    SetConsoleCP(1251);

    vector<string>  dictionary;
    string tmp;

    ifstream input("input.txt");
    if (!input.is_open())
        return 0;

    while (!input.eof())
    {
        getline(input, tmp);
        dictionary.push_back(tmp);
    }
    input.close();
    sort(dictionary.begin(), dictionary.end());

    cout << "Enter the word = ";
    getline(cin, tmp);

    size_t n_words = 1;
    for (auto& it : tmp) if (it == ' ') n_words++;

    vector<vector<string>> correct(n_words);
    for (size_t i = 0; i < n_words; i++)
    {
        string first = tmp.substr(0, tmp.find(' '));
        for (auto& it : dictionary)
            if (is_anagram(first, it))
            {
                correct[i].push_back(it);
            }
        tmp.erase(0, tmp.find(' ') + 1);
    }

    cout << endl << "Result:" << endl;
    f(correct);
    return 0;
}