如何使用'std::next_permutation”和'std::prev_permutation”在 C 中高效生成组合？

在 C 语言中生成组合

问题介绍

生成组合是各种语言中的常见操作编程场景。它包括创建包含来自较大集合的指定数量元素的集合。本文探讨了如何解决在 C 中生成组合的挑战。

使用 std::next_permutation 的解决方案

一种有效的方法是利用 std::next_permutation 函数来自 C 标准库。这是一个实现：

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    int n, r;
    std::cin >> n >> r;

    std::vector<bool> v(n);
    std::fill(v.end() - r, v.end(), true);

    do {
        for (int i = 0; i < n; ++i) {
            if (v[i]) {
                std::cout << (i + 1) << " ";
            }
        }
        std::cout << "\n";
    } while (std::next_permutation(v.begin(), v.end()));
    return 0;
}

此解决方案首先创建一个选择数组 (v) 并将 r 选择器放置在最后 r 个位置。 std::next_permutation 函数生成这些选择器的所有排列。对于每个排列，它都会打印与所选位置相对应的集合成员。

与 std::prev_permutation 替代

对于组合应以不同方式输出的情况顺序，请考虑使用 std::prev_permutation 代替：

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
   int n, r;
   std::cin >> n >> r;

   std::vector<bool> v(n);
   std::fill(v.begin(), v.begin() + r, true);

   do {
       for (int i = 0; i < n; ++i) {
           if (v[i]) {
               std::cout << (i + 1) << " ";
           }
       }
       std::cout << "\n";
   } while (std::prev_permutation(v.begin(), v.end()));
   return 0;
}

此变体会交替顺序的组合，使输出更容易解释。

以上是如何使用'std::next_permutation”和'std::prev_permutation”在 C 中高效生成组合？的详细内容。更多信息请关注PHP中文网其他相关文章！