在 c 中生成组合

Question

我一直在搜索使用 C++ 生成组合的源代码。我为此找到了一些高级代码，但这仅适用于特定数量的预定义数据。任何人都可以给我一些提示，或者可能是产生组合的一些想法。举个例子，假设集合 S = { 1, 2, 3, …., n} 我们从中挑选出 r=2。输入将是 n 和 r 。在这种情况下，程序将生成长度为 2 的数组，如 5 2 输出 1 2、1 3 等。我很难构造算法。我花了一个月的时间思考这个问题。

原文由 Keneth Adrian 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

使用 std::next_permutation 的简单方法：

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

int main() {
    int n, r;
    std::cin >> n;
    std::cin >> 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;
}

或以更易于遵循的顺序输出结果的轻微变化：

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

int main() {
   int n, r;
   std::cin >> n;
   std::cin >> 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;
}

一点解释：

它通过创建一个“选择数组”（ v ）来工作，我们在其中放置 r 选择器，然后我们创建这些选择器的所有排列，如果它被选中则打印相应的集合成员在 v 的当前排列中。希望这可以帮助。

原文由 mitchnull 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

可以直接按字典顺序计算所有组合索引，就像我在下面的代码中所做的那样。

这些索引可用于直接输出或作为指向任何组合项的指针，如 main() 函数的第二个示例中的 "abcde" 字符串，请参见代码后的输出示例。

在线尝试！

 #include <vector>
#include <iostream>

template <typename F>
void Combinations(size_t n, size_t k, F && out) {
    if (k > n)
        return;
    std::vector<size_t> a(k);
    for (size_t i = 0; i < k; ++i)
        a[i] = i;
    while (true) {
        out(a);

        int i = int(k) - 1;
        while (i >= 0 && a[i] >= n - 1 - (k - 1 - i))
            --i;
        if (i < 0)
            break;
        for (size_t j = a[i] + 1; i < k; ++j, ++i)
            a[i] = j;
    }
}

int main() {
    Combinations(5, 3, [](auto const & a){
        for (auto i: a)
            std::cout << i << " ";
        std::cout << std::endl;
    });

    std::string s = "abcde";
    Combinations(5, 3, [&](auto const & a){
        for (auto i: a)
            std::cout << s[i] << " ";
        std::cout << std::endl;
    });
}

输出：

 0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4

a b c
a b d
a b e
a c d
a c e
a d e
b c d
b c e
b d e
c d e

原文由 Arty 发布，翻译遵循 CC BY-SA 4.0 许可协议