C++中排列组合的库函数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2211915/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Library function for Permutation and Combination in C++
提问by skydoor
What's the most widely used existing library in C++ to give all the combination and permutation of k elements out of n elements?
什么是 C++ 中使用最广泛的现有库来给出 n 个元素中 k 个元素的所有组合和排列？
I am not asking the algorithm but the existing library or methods.
我问的不是算法，而是现有的库或方法。
Thanks.
谢谢。
采纳答案by skydoor
Combinations: from Mark Nelson's article on the same topic we have next_combination http://marknelson.us/2002/03/01/next-permutationPermutations: from STL we have std::next_permutation
组合：来自 Mark Nelson 关于同一主题的文章，我们有 next_combination http://marknelson.us/2002/03/01/next-permutation排列：来自 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;
}
回答by Howard Hinnant
I decided to test the solutions by dman and Charles Bailey here. I'll call them solutions A and B respectively. My test is visiting each combination of of a vector<int>size = 100, 5 at a time. Here's the test code:
我决定在这里测试 dman 和 Charles Bailey 的解决方案。我将它们分别称为解决方案 A 和 B。我的测试是一次访问vector<int>大小 = 100、5 的每个组合。这是测试代码：
Test Code
测试代码
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";
}
All code was compiled using clang++ -O3 on a 2.8 GHz Intel Core i5.
所有代码都是在 2.8 GHz Intel Core i5 上使用 clang++ -O3 编译的。
Solution A
方案一
Solution A results in an infinite loop. Even when I make nvery small, this program never completes. Subsequently downvoted for this reason.
解决方案 A 导致无限循环。即使我制作的n很小，这个程序也永远不会完成。后来因为这个原因投了反对票。
Solution B
方案B
This is an edit. Solution B changed in the course of writing this answer. At first it gave incorrect answers and due to very prompt updating it now gives correct answers. It prints out:
这是一个编辑。在撰写此答案的过程中，解决方案 B 发生了变化。起初它给出了不正确的答案，由于非常及时的更新，它现在给出了正确的答案。它打印出：
N = 100, r = 5, visits = 75287520
next_combination total = 4519.84 seconds
next_combination per visit = 60034.3 ns
Solution C
方案C
Next I tried the solution from N2639which looks very similar to solution A, but works correctly. I'll call this solution C and it prints out:
接下来我尝试了N2639的解决方案，它看起来与解决方案 A 非常相似，但工作正常。我将此解决方案称为 C 并打印出：
N = 100, r = 5, visits = 75287520
next_combination total = 6.42602 seconds
next_combination per visit = 85.3531 ns
Solution C is 703 times faster than solution B.
解决方案 C 比解决方案 B 快 703 倍。
Solution D
解决方案 D
Finally there is a solution D found here. This solution has a different signature / style and is called for_each_combination, and is used much like std::for_each. The driver code above changes between the timer calls like so:
最后有一个解决方案 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();
Solution D prints out:
解决方案 D 打印出：
N = 100, r = 5, visits = 75287520
for_each_combination = 0.498979 seconds
for_each_combination per visit = 6.62765 ns
Solution D is 12.9 times faster than solution C, and over 9000 times faster than solution B.
解决方案 D 比解决方案 C 快 12.9 倍，比解决方案 B 快 9000 多倍。
I consider this a relatively small problem: only 75 million visits. As the number of visits increases into the billions, the discrepancy in the performance between these algorithms continues to grow. Solution B is already unwieldy. Solution C eventually becomes unwieldy. Solution D is the highest performing algorithm to visit all combinations I'm aware of.
我认为这是一个相对较小的问题：只有 7500 万次访问。随着访问次数增加到数十亿，这些算法之间的性能差异继续扩大。解决方案 B 已经很笨拙了。解决方案 C 最终变得笨拙。解决方案 D 是访问我所知道的所有组合的最高性能算法。
The link showing solution Dalso contains several other algorithms for enumerating and visiting permutations with various properties (circular, reversible, etc.). Each of these algorithms was designed with performance as one of the goals. And note that none of these algorithms requires the initial sequence to be in sorted order. The elements need not even be LessThanComparable.
显示解决方案 D的链接还包含几种其他算法，用于枚举和访问具有各种属性（圆形、可逆等）的排列。这些算法中的每一个都将性能作为目标之一。请注意，这些算法都不需要初始序列按排序顺序。元素甚至不必是LessThanComparable。
回答by CB Bailey
This answer provides a minimal implementation effort solution. It may not have acceptable performance if you want to retrieve combinations for large input ranges.
这个答案提供了一个最小的实现工作解决方案。如果您想检索大输入范围的组合，它的性能可能无法接受。
The standard library has std::next_permutationand you can trivially build a next_k_permutationfrom it and a next_combinationfrom that.
标准库有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);
}
If you don't have tr1::bindor boost::bindyou would need to build a function object that swaps the arguments to a given comparison. Of course, if you're only interested in a std::lessvariant of next_combinationthen you can use std::greaterdirectly:
如果您没有，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);
}
This is a relatively safe version of next_combination. If you can guarantee that the range [mid, last)is in order as they would be after a call to next_combinationthen you can use the simpler:
这是一个相对安全的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);
}
This also works with bi-directional iterators as well as random access iterators.
这也适用于双向迭代器以及随机访问迭代器。
To output combinations instead of k-permutations, we have to ensure that we output each combination only once, so we'll return a combination it only if it is a k-permutation in order.
要输出组合而不是 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;
}
Alternatives would be to use a reverse iterator instead of the parameter swapping bindcall or to use std::greaterexplicitly if std::lessis the comparison being used.
替代方法是使用反向迭代器而不是参数交换bind调用，或者在使用比较时std::greater显式std::less使用。
回答by AWU
@ Charles Bailey above:
@上面的查尔斯贝利：
I could be wrong, but I think the first two algorithms above does not remove duplicates between first and mid? Maybe I am not sure how to use it.
我可能是错的，但我认为上面的前两个算法不会删除 first 和 mid 之间的重复项？也许我不确定如何使用它。
4 choose 2 example:
1234
1243 (after sort)
1324 (after next_permutation)
1342 (after sort)
1423 (after next_permutation)
1432 (after sort)
2134 (after next_permutation)
4 选择2个例子：
1234
1243（排序后）
1324（next_permutation后）
1342（排序后）
1423（next_permutation后）
1432（排序后）
2134（next_permutation后）
So I added a check to see if the value in italics is in order before returning, but definitely wouldn't have thought of the part you wrote though (very elegant! thanks!).
所以我在返回之前添加了一个检查以查看斜体中的值是否按顺序排列，但绝对不会想到你写的部分（非常优雅！谢谢！）。
Not fully tested, just cursory tests..
没有完全测试，只是粗略的测试..
template
bool next_combination(RandIt first, RandIt mid, RandIt last)
{
typedef typename std::iterator_traits< RandIt >::value_type value_type;
std::sort(mid, last, std::greater< value_type >() );
while(std::next_permutation(first, last)){
if(std::adjacent_find(first, mid, std::greater< value_type >() ) == mid){
return true;
}
std::sort(mid, last, std::greater< value_type >() );
return false;
}
