*1.*原始问题：combination and permutation in C++

What’s the most widely used existing library in C++ to give all the combination and permutation of k elements out of n elements?

I am not asking the algorithm but the existing library or methods.

Thanks.

*2.*被采纳答案

Combinations: from Mark Nelson’s article on the same topic we have next_combination http://marknelson.us/2002/03/01/next-permutation Permutations: from STL we have std::next_permutation

` template `
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;
}

*3.*其他高票答案

*3.1.*第1个答案

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`

size = 100, 5 at a time. Here's the test code:

**Test Code**

```
struct F
{
unsigned long long count_;
F() : count_(0) {}
bool operator()(std::vector
```::iterator, std::vector::iterator)
{++count_; return false;}
};
int main()
{
typedef std::chrono::high_resolution_clock Clock;
typedef std::chrono::duration sec;
typedef std::chrono::duration ns;
int n = 100;
std::vector v(n);
std::iota(v.begin(), v.end(), 0);
std::vector::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.

**Solution A**

Solution A results in an infinite loop. Even when I make `n`

very small, this program never completes. Subsequently downvoted for this reason.

**Solution 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:

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

**Solution C**

Next I tried the solution from N2639 which looks very similar to solution A, but works correctly. I'll call this solution C and it prints out:

```
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.

**Solution 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:

```
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:

```
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.

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.

The link showing solution D also 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`

.

*3.2.*第2个答案

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_permutation`

and you can trivially build a `next_k_permutation`

from it and a `next_combination`

from that.

`template`
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::bind`

or `boost::bind`

you 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::less`

variant of `next_combination`

then you can use `std::greater`

directly:

`template`
bool next_k_permutation(RandIt first, RandIt mid, RandIt last)
{
typedef typename std::iterator_traits::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_combination`

then you can use the simpler:

`template`
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.

`template`
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 `bind`

call or to use `std::greater`

explicitly if `std::less`

is the comparison being used.

*3.3.*第3个答案

@ 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.

4 choose 2 example:

*12* 34

*12* 43 (after sort)

*13* 24 (after next_permutation)

*13* 42 (after sort)

*14* 23 (after next_permutation)

*14* 32 (after sort)

*21* 34 (after 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;
}
```

转载请注明：CodingBlog » C++中的排列组合