如何在 C++ 中更有效地生成这么多排列？

Question

我正在尝试解决一个问题，我觉得我真的很接近它了，但它仍然有点慢，因为我生成了太多的排列。

我需要“0123456789”的排列。我知道有很多 (10)! 排列。我使用 std::unordered_set 因为我不关心它们的存储顺序而且它似乎比使用常规 std::set

更快

这是我写的一些核心： max_perm_size 是我在特定情况下关心的排列字符串的大小。

void getPermutations(unordered_set<string> &permutations, int &max_perm_size)
{
    string digits = "0123456789";

    do{

        permutations.insert(digits.substr(0, max_perm_size));

    } while (next_permutation(digits.begin(), digits.end()));

}

关于这段代码我有两个主要问题：

以上我仍然生成整个“0123456789”排列，即使在我只关心大小排列 max_perm_size 的情况下也是如此。在将它们存储到我的 std::unordered_set 之前，我只是 trim 它们的后记。有没有更好的方法可以更快地完成此操作？
对于最坏的情况max_pem_size = 10，有没有更有效的方法来生成和存储所有这些一般排列？

Answer 1

您可以先取数字字符串的子字符串。那么你的循环将只处理 max_perm_size.
您可以创建一个 class 来按需生成排列，而不是预先生成并存储它们。根据您的应用程序，您甚至可能不必存储它们。

Answer 2

这是针对你的情况的，不是通用的解决方案，但对于数字排列的情况，你可以这样做：

void getPermutations(unordered_set<string> &permutations, int max_perm_size)
{
    if (max_perm_size < 1) return;

    uint64_t stopat = 1;
    for (int i = 1; i < max_perm_size; ++i) {
        stopat *= 10;
    }

    for (uint64_t dig = 0; dig < stopat; ++dig) {
        std::ostringstream ss;
        ss << std::setw(max_perm_size) << std::setfill('0') << dig;
        permutations.insert(ss.str());
    }
}

Answer 3

据我所知，您的结果是从 0 到某个限制的数字（没有重复数字）。既然你说你不关心数字的顺序，那么如果我们只坚持升序可能是最简单的。既然如此，我们可以生成这样的结果：

#include <iostream>

int main() {
    for (int i=0; i<10; i++)
        for (int j=i+1; j<10; j++)
            for (int k=j+1; k<10; k++)
                std::cout << i << j << k << "\t";
}

结果：

012     013     014     015     016     017     018     019     023     024     025     026     027
028     029     034     035     036     037     038     039     045     046     047     048     049
056     057     058     059     067     068     069     078     079     089     123     124     125
126     127     128     129     134     135     136     137     138     139     145     146     147
148     149     156     157     158     159     167     168     169     178     179     189     234
235     236     237     238     239     245     246     247     248     249     256     257     258
259     267     268     269     278     279     289     345     346     347     348     349     356
357     358     359     367     368     369     378     379     389     456     457     458     459
467     468     469     478     479     489     567     568     569     578     579     589     678
679     689     789

如果您的限制不是数字的数量，您可以将这些数字组合成一个实际的 int 并进行比较（然后跳出循环）。

如何在 C++ 中更有效地生成这么多排列？

How to generate only so many permutations more efficiently in C++?

c++

algorithm

optimization

permutation

unordered-set