C++中的组合和排列

Question

什么是C++中使用最广泛的现有库来提供n个元素中k个元素的所有组合和排列？

我不是问算法而是现有的库或方法.

谢谢.

Answer 1

我决定在这里测试dman和Charles Bailey的解决方案.我将分别称它们为解决方案A和B. 我的测试是每次访问vector<int>大小= 100,5的每个组合.这是测试代码:

测试代码

struct F
{
    unsigned long long count_;

    F() : count_(0) {}

    bool operator()(std::vector<int>::iterator, std::vector<int>::iterator)
    {++count_; return false;}
};

int main()
{
    typedef std::chrono::high_resolution_clock Clock;
    typedef std::chrono::duration<double> sec;
    typedef std::chrono::duration<double, std::nano> ns;
    int n = 100;
    std::vector<int> v(n);
    std::iota(v.begin(), v.end(), 0);
    std::vector<int>::iterator r = v.begin() + 5;
    F f;
    Clock::time_point t0 = Clock::now();
    do
    {
        f(v.begin(), r);
    } while (next_combination(v.begin(), r, v.end()));
    Clock::time_point t1 = Clock::now();
    sec s0 = t1 - t0;
    ns pvt0 = s0 / f.count_;
    std::cout << "N = " << v.size() << ", r = " << r-v.begin()
              << ", visits = " << f.count_ << '\n'
              << "\tnext_combination total = " << s0.count() << " seconds\n"
              << "\tnext_combination per visit = " << pvt0.count() << " ns";
}

所有代码都是在2.8 GHz Intel Core i5上使用clang ++ -O3编译的.

解决方案A.

解决方案A导致无限循环.即使我n做得很小,这个程序也永远不会完成.随后因为这个原因而被投票.

解决方案B.

这是一个编辑.解决方案B在写这个答案的过程中改变了.起初它给出了错误的答案,并且由于非常迅速的更新,它现在给出了正确的答案.打印出来:

N = 100, r = 5, visits = 75287520
    next_combination total = 4519.84 seconds
    next_combination per visit = 60034.3 ns

解决方案C.

接下来我尝试了N2639的解决方案,它看起来与解决方案A非常相似,但工作正常.我将这个解决方案称为C并打印出来:

N = 100, r = 5, visits = 75287520
    next_combination total = 6.42602 seconds
    next_combination per visit = 85.3531 ns

解决方案C比解决方案B快703倍.

解决方案D.

最后是找到了解决方案d 这里.此解决方案具有不同的签名/样式,并且被称为for_each_combination,并且使用非常类似std::for_each.上面的驱动代码在定时器调用之间发生变化,如下所示

Clock::time_point t0 = Clock::now();
f = for_each_combination(v.begin(), r, v.end(), f);
Clock::time_point t1 = Clock::now();

解决方案D打印出来:

N = 100, r = 5, visits = 75287520
    for_each_combination = 0.498979 seconds
    for_each_combination per visit = 6.62765 ns

溶液D比溶液C快12.9倍,比溶液B快9000倍.

我认为这是一个相对较小的问题:只有7500万次访问.随着访问次数增加到数十亿,这些算法之间的性能差异继续增长.解决方案B已经很笨拙.解决方案C最终变得笨拙.解决方案D是访问我所知道的所有组合的性能最高的算法.

显示解D的链接还包含几个其他算法,用于枚举和访问具有各种属性(循环,可逆等)的排列.这些算法中的每一个都被设计为性能作为目标之一.请注意,这些算法都不要求初始序列按排序顺序排列.元素甚至不需要LessThanComparable.

Answer 2

组合:来自Mark Nelson关于同一主题的文章我们有next_combination http://marknelson.us/2002/03/01/next-permutation Permutations:来自STL我们有std :: next_permutation

   template <typename Iterator>
   inline bool next_combination(const Iterator first, Iterator k, const Iterator last)
   {
      if ((first == last) || (first == k) || (last == k))
         return false;
      Iterator itr1 = first;
      Iterator itr2 = last;
      ++itr1;
      if (last == itr1)
         return false;
      itr1 = last;
      --itr1;
      itr1 = k;
      --itr2;
      while (first != itr1)
      {
         if (*--itr1 < *itr2)
         {
            Iterator j = k;
            while (!(*itr1 < *j)) ++j;
            std::iter_swap(itr1,j);
            ++itr1;
            ++j;
            itr2 = k;
            std::rotate(itr1,j,last);
            while (last != j)
            {
               ++j;
               ++itr2;
            }
            std::rotate(k,itr2,last);
            return true;
         }
      }
      std::rotate(first,k,last);
      return false;
   }

Answer 3

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

标准库有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是比较则显式使用.