Generating combinations in c++

by

A simple way using 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;
}

or a slight variation that outputs the results in an easier to follow order:

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

A bit of explanation:

It works by creating a “selection array” (v), where we place r selectors, then we create all permutations of these selectors, and print the corresponding set member if it is selected in in the current permutation of v. Hope this helps.

More Related Contents:

  1. Creating all possible k combinations of n items in C++
  2. Howto create combinations of several vectors without hardcoding loops in C++?
  3. What’s time complexity of this algorithm for finding all combinations?
  4. Insertion sort stops working after million input
  5. How to find out how many bits are set (equal 1) in the product of two integers [closed]
  6. C++ – Find numbers between first and last negative numbers in Array
  7. Image Processing: Algorithm Improvement for ‘Coca-Cola Can’ Recognition
  8. Calculating pow(a,b) mod n
  9. Rotating a point about another point (2D)
  10. Create Random Number Sequence with No Repeats
  11. Finding duplicates in O(n) time and O(1) space
  12. Getting the actual length of a UTF-8 encoded std::string?
  13. Algorithm for finding the smallest power of two that’s greater or equal to a given value [duplicate]
  14. How can I find the actual path found by BFS?
  15. Splitting a string by a character
  16. How can I sort a std::map first by value, then by key?
  17. Iterative DFS vs Recursive DFS and different elements order
  18. what is the difference between set and unordered_set in C++?
  19. Similar String algorithm
  20. Calculating the Amount of Combinations
  21. Searching in a sorted and rotated array
  22. Better shading on BW display while rendering filled surfaces
  23. `std::list::sort()` – why the sudden switch to top-down strategy?
  24. Algorithm to add or subtract days from a date?
  25. Easiest way of using min priority queue with key update in C++
  26. Creating N nested for-loops
  27. Edges on polygon outlines not always correct
  28. How to find Longest Common Substring using C++
  29. Fastest way to get the integer part of sqrt(n)?
  30. Generate N random numbers within a range with a constant sum

Leave a Comment