Trying to simulate python combinations in C++ with next_permutation

Question

I need to port a snippet written in Python to C++ but that snippet is using combinations from itertools in python.

The line that I'm really interested to porting over to C++ is this one:

for k in combinations(range(n-i),2*i):

range(n-i) in Python will generate a list from 0 to (n-i) - 1

Let n = 16, i = 5

print range(n-i)

outputs:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

and python combinations will generate all possible combinations in that list.

e.g.

print list(combinations(range(n-i),2*i))

outputs:

[(0, 1, 2, 3, 4, 5, 6, 7, 8, 9),
(0, 1, 2, 3, 4, 5, 6, 7, 8, 10),
(0, 1, 2, 3, 4, 5, 6, 7, 9, 10),
(0, 1, 2, 3, 4, 5, 6, 8, 9, 10),
(0, 1, 2, 3, 4, 5, 7, 8, 9, 10),
(0, 1, 2, 3, 4, 6, 7, 8, 9, 10),
(0, 1, 2, 3, 5, 6, 7, 8, 9, 10),
(0, 1, 2, 4, 5, 6, 7, 8, 9, 10),
(0, 1, 3, 4, 5, 6, 7, 8, 9, 10),
(0, 2, 3, 4, 5, 6, 7, 8, 9, 10),
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)]

I want to generate similar output using std::vector and next_permutation from C++ but I'm still getting erroneous results. This is my current approach:

for(int j = 0; j < n-i; j++) {
        temp_vector.push_back(j); 
}

That snippet is equivalent to range(n-i) in Python.

But the following snippet:

do {
     myvector.push_back(temp_vector);
} while(next_permutation(temp_vector.begin(),temp_vector.begin()+2*i));
cout<<myvector.size()<<endl;

Is not equivalent to combinations(range(n-i),2*i)) in Python, and I've tried many variations and still haven't been able to come up with the results I'm expecting.

For example:

Let n = 16 i = 5

Python

>>> print len(list(combinations(range(n-i),2*i)))

11

C++

#include <vector>
#include <iostream>

using namespace std;
int main() {
    vector<int> temp_vector;
    vector< vector<int> > myvector;
    int n = 16, i = 5;
    for(int j = 0; j < n - i; j++) {
            temp_vector.push_back(j);
    }
    do {
            myvector.push_back(temp_vector);
    } while(next_permutation(temp_vector.begin(), temp_vector.begin()+2*i));
    cout<<myvector.size()<<endl;
    return 0;
}

g++ combinations.cpp

./a.out

3628800

Any guidance will be greatly appreciated! Thanks a lot!

Answer 1

combinations and permutations are not the same thing.

A combination is an unordered list of a subset of the items from another set. A permutation is a unique order of the items in the list.

You're generating all combinations of 10 things from a list of 11 things, so you'll get 11 results, each one missing a different one of the original 11 items.

Generating every permutation will generate every unique order of the original 11 items. Since the items in this case are all unique that means the result would be 11! lists where each contains all 11 items. You're only generating permutations from the first 10 items however, so you're getting 10! lists, none of which contain the 11th item.

You need to find an algorithm for generating combinations instead of permutations.

---

There's no built-in algorithm for combinations. std::next_permutation can be used as part of an algorithm to generate combinations: See Generating combinations in c++.

Here's an old draft proposal for algorithms for combinations, including code.