我需要将用Python编写的代码段移植到C ++,但该代码片段使用python中的itertools组合。
我真正有兴趣移植到C ++的那一行是这样的:
for k in combinations(range(n-i),2*i):
Python中的range(n-i)
将从0 to (n-i) - 1
生成一个列表
设n = 16,i = 5
print range(n-i)
输出:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
和python组合将生成该列表中的所有可能组合。
EG
print list(combinations(range(n-i),2*i))
输出:
[(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)]
我想使用来自C ++的std::vector
和next_permutation
生成类似的输出,但我仍然得到错误的结果。这是我目前的做法:
for(int j = 0; j < n-i; j++) {
temp_vector.push_back(j);
}
该片段相当于Python中的range(n-i)
。
但是以下片段:
do {
myvector.push_back(temp_vector);
} while(next_permutation(temp_vector.begin(),temp_vector.begin()+2*i));
cout<<myvector.size()<<endl;
不等于Python中的combinations(range(n-i),2*i))
,我尝试了很多变化,但仍未能提出我期待的结果。
例如:
设n = 16 i = 5
蟒蛇
>>> 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
任何指导将不胜感激!非常感谢!
组合和排列不是一回事。
组合是来自另一组的项的子集的无序列表。排列是列表中项目的唯一顺序。
你从11个事物的列表中生成10件事的所有组合,所以你将获得11个结果,每个结果都缺少原始11个项目中的不同结果。
生成每个排列将生成原始11项的每个唯一顺序。由于这种情况下的项目都是唯一的,这意味着结果将是11!列出每个包含所有11个项目的列表。你只是从前10个项目中产生排列,所以你得到10个!列表,其中没有一个包含第11项。
您需要找到一种算法来生成组合而不是排列。
组合没有内置算法。 std :: next_permutation可用作生成组合的算法的一部分:请参阅Generating combinations in c++。
Here's是一个关于组合算法的旧提案,包括代码。