C++ 字符串的排列，输出结果小于或等于字符串的长度

Question

有没有一种方法可以让我使用排列来得到小于想要排列的字符串的结果？

例如，如果用户输入一串字符，假设是“dvoig”。在 C++ 中，如果我使用 next_permutation，它只会遍历这 5 个字母。所以我会得到如下输出； voidg、divgo、ovgid 等

到目前为止，这是我通常建议的代码:

int main()
{
    string str;
    cout << "Enter the string : ";
    cin >> str;
    sort(str.begin(), str.end()); 
    do {
        cout << str << endl;
    } while (next_permutation(str.begin(), str.end()));
}

但是我也想要小于 5 的输出，例如； void、divg、ovgi、dog、odg、oid、div、iv、go、do 等。这甚至可能吗？如果可以，我该如何实现？

在过去的 12 个小时里，我一直试图让一些东西工作但无济于事，我开始感到压力很大。

谢谢大家的帮助，我们将不胜感激。

Answer 1

您可以在 next_permutation 返回的每个字符串上使用 substr 来获取子字符串。然后，您可以使用一个集合来聚合所有排列中的所有字符串，这些排列会自动为您处理重复项。这样的事情会起作用:

#include<iostream>
#include<string>
#include<algorithm>
#include<unordered_set>

int main()
{
    std::string str;
    std::unordered_set<std::string> permutations;

    std::cout << "Enter the string : ";
    std::cin >> str;
    std::sort(str.begin(), str.end());
    unsigned int length = str.length();
    do {
        for (unsigned int i = 0; i < length; i++)
        {
            permutations.insert(str.substr(0, length - i - 1));
        }
    } while (std::next_permutation(str.begin(), str.end()));

    std::for_each(permutations.begin(), permutations.end(), [](std::string permutation) {
        std::cout << permutation << std::endl;
    });

    return 0;
}