C++ 中 n 次单项式的组合
Combinations of n-th degree monomials in C++
所以我必须生成一个单项式向量。以下是我如何为任意顺序处理最多 3 个维度:
#include <iostream>
#include <vector>
using namespace std;
int main() {
int dim = 3;
int order = 2;
std::vector<std::vector<int>> powers;
for (int ord = 0; ord <= order; ord++) {
if (dim == 1) {
powers.push_back({ord});
} else if (dim == 2) {
for (int i = 0; i < ord + 1; i++) {
powers.push_back({i, ord - i});
}
} else if (dim == 3) {
for (int i = 0; i < ord + 1; i++) {
for (int j = 0; j < ord + 1 - i; j++) {
powers.push_back({i, j, ord - i - j});
}
}
} else if (dim == 4){
for (int i = 0; i < ord + 1; i++) {
for (int j = 0; j < ord + 1 - i; j++) {
for (int k = 0; k < ord + 1 - i - j; k++) {
powers.push_back({i, j, k, ord - i - j - k});
}
}
}
} else {
// "Monomials of dimension >= 4 not supported."
}
}
cout << "Finished!" << endl;
return 0;
}
现在我的目标是支持 N 维和 N 阶单项式。关于如何将上面的代码扩展到 N 维空间的任何想法?
我没有看到一种简单的方法来实现上面的内容。我正在考虑使用组合数学并以某种方式消除额外的项,但我不确定速度。
编辑(预期输出):
对于给定的输入 order = 2
和 dim = 3
,预期的输出是(按该顺序不需要):
000
001
002
010
011
020
100
101
110
200
对于 order = 1
和 dim = 3
:
000
001
010
100
以及 order = 2
和 dim = 2
:
00
01
10
11
02
20
这是一个经典的递归函数:
每次您必须选择当前变量的顺序 x_1(假设为 i),然后您将保留在 n -1 个变量上具有阶数 ord - i 的单项式的所有可能性。
(工作)代码如下:
std::vector<std::vector<int>> getAllMonomials(int order, int dimension) {
std::vector<std::vector<int>> to_return;
if (1 == dimension) {
for (int i = 0 ; i <= order; i++){
to_return.push_back({i});
}
return to_return;
}
for (int i = 0 ; i <= order; i++) {
std::vector<std::vector<int>> all_options_with_this_var_at_degree_i = getAllMonomials(order - i, dimension - 1);
for (int j = 0; j < all_options_with_this_var_at_degree_i.size(); j++) {
all_options_with_this_var_at_degree_i.at(j).insert(all_options_with_this_var_at_degree_i.at(j).begin(), i);
}
to_return.insert(to_return.end(), all_options_with_this_var_at_degree_i.begin(), all_options_with_this_var_at_degree_i.end());
}
return to_return;
}
Pyrhon递归求解
def compose(leng, summ, res):
if leng == 0:
print(res)
return
for i in range(summ + 1):
compose(leng - 1, summ -i, res + str(i) + " ")
compose(3, 2, "")
所以我必须生成一个单项式向量。以下是我如何为任意顺序处理最多 3 个维度:
#include <iostream>
#include <vector>
using namespace std;
int main() {
int dim = 3;
int order = 2;
std::vector<std::vector<int>> powers;
for (int ord = 0; ord <= order; ord++) {
if (dim == 1) {
powers.push_back({ord});
} else if (dim == 2) {
for (int i = 0; i < ord + 1; i++) {
powers.push_back({i, ord - i});
}
} else if (dim == 3) {
for (int i = 0; i < ord + 1; i++) {
for (int j = 0; j < ord + 1 - i; j++) {
powers.push_back({i, j, ord - i - j});
}
}
} else if (dim == 4){
for (int i = 0; i < ord + 1; i++) {
for (int j = 0; j < ord + 1 - i; j++) {
for (int k = 0; k < ord + 1 - i - j; k++) {
powers.push_back({i, j, k, ord - i - j - k});
}
}
}
} else {
// "Monomials of dimension >= 4 not supported."
}
}
cout << "Finished!" << endl;
return 0;
}
现在我的目标是支持 N 维和 N 阶单项式。关于如何将上面的代码扩展到 N 维空间的任何想法? 我没有看到一种简单的方法来实现上面的内容。我正在考虑使用组合数学并以某种方式消除额外的项,但我不确定速度。
编辑(预期输出):
对于给定的输入 order = 2
和 dim = 3
,预期的输出是(按该顺序不需要):
000
001
002
010
011
020
100
101
110
200
对于 order = 1
和 dim = 3
:
000
001
010
100
以及 order = 2
和 dim = 2
:
00
01
10
11
02
20
这是一个经典的递归函数:
每次您必须选择当前变量的顺序 x_1(假设为 i),然后您将保留在 n -1 个变量上具有阶数 ord - i 的单项式的所有可能性。
(工作)代码如下:
std::vector<std::vector<int>> getAllMonomials(int order, int dimension) {
std::vector<std::vector<int>> to_return;
if (1 == dimension) {
for (int i = 0 ; i <= order; i++){
to_return.push_back({i});
}
return to_return;
}
for (int i = 0 ; i <= order; i++) {
std::vector<std::vector<int>> all_options_with_this_var_at_degree_i = getAllMonomials(order - i, dimension - 1);
for (int j = 0; j < all_options_with_this_var_at_degree_i.size(); j++) {
all_options_with_this_var_at_degree_i.at(j).insert(all_options_with_this_var_at_degree_i.at(j).begin(), i);
}
to_return.insert(to_return.end(), all_options_with_this_var_at_degree_i.begin(), all_options_with_this_var_at_degree_i.end());
}
return to_return;
}
Pyrhon递归求解
def compose(leng, summ, res):
if leng == 0:
print(res)
return
for i in range(summ + 1):
compose(leng - 1, summ -i, res + str(i) + " ")
compose(3, 2, "")