Print all subsets of given size of a set and count the subset

Question

Generate all possible subset of size r of given array with distinct elements. i need help for counting the subset after getting all possible subset of size r of given array with distinct elements. how to count the subset of distinct element after generated

    #include <bits/stdc++.h> 
    using namespace std;
    void combinationUtil(int arr[], int n, int r, int index, int data[], int i); 

    void printCombination(int arr[], int n, int r) 
    { 
        int data[r]; 

        combinationUtil(arr, n, r, 0, data, 0); 
    } 
    void combinationUtil(int arr[], int n, int r, int index,int data[], int i) 
    { 
        int c=0; 
        if (index == r) { 
            for (int j = 0; j < r; j++) {
                printf("%d ", data[j]); 
            }
            printf("\n"); 
            return; 
        } 

        if (i >= n) 
            return; 

        data[index] = arr[i]; 
        combinationUtil(arr, n, r, index + 1, data, i + 1); 
        combinationUtil(arr, n, r, index, data, i + 1); 
    } 

    int main() 
    { 
        int arr[] = { 0,1,2,3,4}; 
        int r = 2; 
        int n = sizeof(arr) / sizeof(arr[0]); 
        printCombination(arr, n, r); 
        return 0; 
    }

output 
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4
number of subset 10

1) `int data[r];` -- This is not valid C++. 2) `#include ` -- Use the proper headers, not this one. 3) This problem is solved by using `std::next_permutation` along with a few other items, all without recursion. — PaulMcKenzie, Sep 15 '19 at 18:31
[Possible duplicate](https://stackoverflow.com/questions/9430568/generating-combinations-in-c) — PaulMcKenzie, Sep 15 '19 at 18:37
Possible duplicate of [Generating combinations in c++](https://stackoverflow.com/questions/9430568/generating-combinations-in-c) — S.S. Anne, Oct 12 '19 at 13:03

Jonathan Mee · Answer 1 · 2019-09-15T19:03:28.390

0

Let's solve this with: next_permutation. This will permute an input, returning false when all permutations have been visited.
Given the sorted input: int arr[] we can do:

do {
    copy(cbegin(arr), cend(arr), ostream_iterator<int>(cout, " "));
    cout << endl;
} while(next_permutation(begin(arr), end(arr)));

Live Example

This example assumes unique inputs, in which case a combination and permutation are the same. If you don't have unique inputs you're really asking for a combination of these numbers. next_combination has been purposed here: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2639.pdf You can copy that implementation if you find that you won't have unique inputs and just use that. You can also find out more about next_combination here: https://stackoverflow.com/a/35215540/2642059

edited Sep 15 '19 at 19:03

answered Sep 15 '19 at 18:42

Jonathan Mee

36,513
20
115
270

Yes, but I think the OP wanted combinations. You still use `next_permutation`, but the permutation will be on the boolean array that points to certain values in `arr`. – PaulMcKenzie Sep 15 '19 at 18:50
That is fair, I am presuming unique numbers. I'll update to clarify. – Jonathan Mee Sep 15 '19 at 18:52
#include #include #include int main() { int n, r; std::cin >> n; std::cin >> r; std::vector v(n); std::fill(v.begin(), v.begin() + 2, true); int c=0; do { for (int i = 0; i < n; ++i) { if (v[i]) { std::cout << (i) << " "; } } std::cout << "\n"; c++; } while (std::prev_permutation(v.begin(), v.end())); std::cout< – chitaranjan pradhan Sep 15 '19 at 18:56
1

@chitaranjanpradhan -- Post code either in the original question, or if you have an answer, post it in a separate answer. Don't post all of that code in the comment section. – PaulMcKenzie Sep 15 '19 at 18:59
@chitaranjanpradhan So it looks like as has been stated in the comments that you are looking for `next_combination` not `next_permutation`. Sadly this hasn't been accepted into the standard yet. When I've needed it I've just copied the implementation out of that proposal and used it. – Jonathan Mee Sep 15 '19 at 19:08
@PaulMcKenzie Welp, after the follow up comment it looks like you were dead on. I've updated the question, but it's sad that we haven't gotten `next_combination` yet :( – Jonathan Mee Sep 15 '19 at 19:11

Print all subsets of given size of a set and count the subset

1 Answers1