gpt4 book ai didi

c++ - 尝试使用 next_permutation 在 C++ 中模拟 python 组合

转载 作者:太空狗 更新时间:2023-10-29 21:03:26 25 4
gpt4 key购买 nike

我需要将用 Python 编写的片段移植到 C++但该片段使用了 python 中 itertools 的组合。

我真正有兴趣移植到 C++ 的是这一行:

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

range(n-i) 将生成一个从 0 到 (n-i) - 1

的列表

令 n = 16, i = 5

打印范围(n-i)

输出:

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

和 python 组合将生成该列表中所有可能的组合。

例如

打印列表(组合(范围(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)]

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);
}

该片段相当于 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我 = 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++ 组合.cpp

./a.out

3628800

任何指导将不胜感激!非常感谢!

最佳答案

组合和排列不是一回事。

组合是另一组项目子集的无序列表。排列是列表中项目的唯一顺序。

您要从包含 11 个事物的列表中生成 10 个事物的所有组合,因此您将获得 11 个结果,每个结果都缺少原始 11 个项目中的不同项目。

生成每个排列将生成原始 11 项的每个唯一顺序。由于本例中的项目都是唯一的,这意味着结果将是 11!列出其中每个包含所有 11 项的列表。但是,您只是从前 10 个项目生成排列,所以您得到 10 个!列表,其中都不包含第 11 项。

您需要找到一种算法来生成组合而不是排列。


组合没有内置算法。 std::next_permutation 可用作生成组合的算法的一部分:参见 Generating combinations in c++ .

Here's组合算法的旧提案草案,包括代码。

关于c++ - 尝试使用 next_permutation 在 C++ 中模拟 python 组合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13423383/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com