How Can I Efficiently Generate Combinations in C Using `std::next_permutation` and `std::prev_permutation`?

Generating Combinations in C

Problem Introduction

Generating combinations is a common operation in various programming scenarios. It consists of creating sets containing a specified number of elements from a larger collection. This article explores how to tackle the challenge of generating combinations in C .

Solution with std::next_permutation

One effective approach is to leverage the std::next_permutation function from the C Standard Library. Here's an implementation:

#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;
}

This solution begins by creating a selection array (v) and placing r selectors in the last r positions. The std::next_permutation function generates all permutations of these selectors. For each permutation, it prints the set members corresponding to the selected positions.

Alternative with std::prev_permutation

For situations where the combinations should be output in a different order, consider using std::prev_permutation instead:

#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;
}

This variation alternates the order of the combinations, making the output easier to interpret.

The above is the detailed content of How Can I Efficiently Generate Combinations in C Using `std::next_permutation` and `std::prev_permutation`?. For more information, please follow other related articles on the PHP Chinese website!