C ++中的组合和排列

Question

C ++中的组合和排列什么是C ++中使用最广泛的现有库来提供n个元素中k个元素的所有组合和排列？我不是问算法而是现有的库或方法。谢谢。

Answer 1

此答案提供了最小的实施工作解决方案。如果要检索大输入范围的组合，则可能没有可接受的性能。

标准库有std::next_permutation，你可以从中轻松地构建一个next_k_permutation和它next_combination。

template<class RandIt, class Compare>bool next_k_permutation(RandIt first, RandIt mid, RandIt last, Compare comp){
    std::sort(mid, last, std::tr1::bind(comp, std::tr1::placeholders::_2                                            , std::tr1::placeholders::_1));
    return std::next_permutation(first, last, comp);}

如果您没有tr1::bind或者boost::bind您需要构建一个将参数交换为给定比较的函数对象。当然，如果您只对某种std::less变体感兴趣，next_combination可以std::greater直接使用：

template<class RandIt>bool next_k_permutation(RandIt first, RandIt mid, RandIt last){
    typedef typename std::iterator_traits<RandIt>::value_type value_type;

    std::sort(mid, last, std::greater< value_type >());
    return std::next_permutation(first, last);}

这是一个相对安全的版本next_combination。如果您可以保证范围[mid, last)与调用之后的顺序一致，next_combination那么您可以使用更简单的：

template<class BiDiIt, class Compare>bool next_k_permutation(BiDiIt first, BiDiIt mid, BiDiIt last, Compare comp){
    std::reverse(mid, last);
    return std::next_permutation(first, last, comp);}

这也适用于双向迭代器以及随机访问迭代器。

要输出组合而不是k-排列，我们必须确保只输出每个组合一次，所以只有当它是按顺序的k排列时，我们才会返回它的组合。

template<class BiDiIt, class Compare>bool next_combination(BiDiIt first, BiDiIt mid, BiDiIt last, Compare comp){
    bool result;
    do
    {
        result = next_k_permutation(first, mid, last, comp);
    } while (std::adjacent_find( first, mid,
                             std::tr1::bind(comp, std::tr1::placeholders::_2                                                , std::tr1::placeholders::_1) )
                                                                        != mid );
    return result;}

替代方案是使用反向迭代器而不是参数交换bind调用，或者std::greater如果使用的std::less是比较则显式使用。