CODEWITHSUNDEEP
c++
user13757050
user13757050

Reputation:

Using next_permutation to get all combinations of length N C++

I am trying to do the classic all combinations of a list problem and I found this code here on the forum that works wonderful. However, I would like to limit the combinations to N elements. I know there are many similar threads but I am yet to find a simple solution to this issue. Are there any simple solutions to this that doesn't require adding a lot of new lines of code?

std::string next() {
    int n = 2; // Will only give me combinations of length 2
    std::vector<std::string> arr = { "a", "b", "c", "d", "e" };
    std::sort(arr.begin(), arr.end()); 
    do {
        for(auto& i: arr)
            std::cout << i;
        std::cout << '\n';
    } while(std::next_permutation(arr.begin(), arr.end()));  
}

Upvotes: 0

Views: 1442

Answers (1)

463035818_is_not_an_ai
463035818_is_not_an_ai

Reputation: 123431

The most simple is to use only the first two elements of any permutation and skip duplicates. To have uniques you can use a std::set:

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


void next() {
    int n = 2; // Will only give me combinations of length 2
    std::vector<std::string> arr = { "a", "b", "c", "d", "e" };
    std::sort(arr.begin(), arr.end()); 
    
    std::set<std::vector<std::string>> result;
    
    do {
        result.emplace(arr.begin(),arr.begin()+n);
    } while(std::next_permutation(arr.begin(), arr.end()));  

    for (const auto& c : result) {
        for (const auto& e : c) std::cout << e ;
        std::cout << '\n';
    }
}

int main() {
    next();
}

Output:

ab
ac
ad
ae
ba
bc
bd
be
ca
cb
cd
ce
da
db
dc
de
ea
eb
ec
ed

PS: Your function is declared to return a std::string but it does not return anything. This is undefined behavior. When I tried to run it I got a double free runtime error.

Upvotes: 2

Related Questions