时间戳

首页 > 解决方案 > 使用 next_permutation 获取长度为 N C++的所有组合

c++ - 使用 next_permutation 获取长度为 N C++的所有组合

问题描述

我正在尝试执行列表问题的经典所有组合，并且我在论坛上发现此代码非常有效。但是，我想将组合限制为 N 个元素。我知道有很多类似的线程，但我还没有找到解决这个问题的简单方法。有没有不需要添加很多新代码行的简单解决方案？

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()));  
}

标签： c++

解决方案

最简单的是只使用任何排列的前两个元素并跳过重复项。要拥有唯一性，您可以使用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();
}

输出：

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

PS：您的函数被声明为返回 astd::string但它不返回任何内容。这是未定义的行为。当我尝试运行它时，我得到了一个双重免费运行时错误。

推荐阅读