C++ - 如何遍历数组的所有组合以进行暴力破解
C++ - How to iterate through all of the combinations of an array for bruteforcing
我有一个练习，找出 1-9 的所有可能总和，加起来等于 100，规则是每个数字必须按顺序使用一次，允许的运算符是 +/- 并添加数字在一起，例如。 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100
我已经写出了解决这个问题的逻辑，我有一个包含 9 个元素的数组，代表可以放置运算符的所有位置，1 个是 +，2 个是 -，3 个是数字相加.
上述示例的运算符字符串为 {1,1,1,2,1,1,1,3,1}.
所以我真正的问题是如何遍历这个运算符数组并生成每个可能的数字组合。
所以我从
{1,1,1,1,1,1,1,1,1}
然后像这样前进，直到数组全是 3
111111111
111111112
111111113
111111121
111111122
111111123
111111131
我在去年左右为此编写了一个函数，但它使用了很多 if else 语句，使该函数不灵活，我想就执行此操作的正确步骤提出建议，因为我想改进我的编码。
OP 非常公正地指出问题是关于家庭作业的
I have a exercise finding all of the possible sums of 1-9 that add up to 100
因此，我没有提供此练习的完整解决方案，而是提供了一些不需要添加太多内容即可实现的解决方案。
给出了九个参数（数字 1 … 9），它们是二元运算符的参数。
二元运算符需要一个左右参数。因此，我得出结论，有 8 个位置可以选择二元运算符。
这对于 + 和 - 来说很容易，但是 添加数字 呢？
这是一个我称之为“连接”的操作。实际上，将“连接”表示为简单的算术表达式很容易：
lr: 10 * l + r
“串联”问题解决后，就没那么复杂了
我的第一个想法是使用仿函数或函数指针之类的东西，但没有它也不难解决。
为此，我定义了一个操作枚举：
enum Op { Add, Sub, Cat, NOps};
和用于这些操作的 compute() 函数：
int compute(Op op, int l, int r)
{
switch (op) {
case Add: return l + r;
case Sub: return l - r;
case Cat: return l * 10 + r;
}
// ...unreachable for the humans eyes but not for the compiler...
assert(false); return 0;
}
下一个拼图是计算完整方程结果的函数。
该等式由 N 个参数（数字）和 N - 1 个运算符定义。
在执行此操作时，我意识到“串联”必须具有更高的优先级。否则，计算功能将无法正常工作。
示例：
12 + 23 = 35
如果不考虑“连接”的更高优先级，这将导致：
12 + 23 = ((12) + 2)3 = (14)3 = 143
对于这个问题的简单解决方案，计算函数应该运行两次：
- 解析所有连接
- 解决所有其他操作。
int compute(std::vector<int> args, std::vector<Op> &ops)
{
assert(args.size() == ops.size() + 1);
// perform cat()
std::vector<int> args2;
args2.push_back(args[0]);
for (size_t i = 0, n = ops.size(); i < n; ++i) {
if (ops[i] == Cat) {
int l = args2.back(); args2.pop_back();
args2.push_back(compute(Cat, l, args[i + 1]));
} else args2.push_back(args[i + 1]);
}
// perform add() and sub()
int result = args2[0];
for (size_t i = 0, j = 1, n = ops.size(); i < n; ++i) {
const Op op = ops[i];
if (op != Cat) result = compute(op, result, args2[j++]);
}
return result;
}
最后缺失的部分是 std::vector<Op> &ops 中值的 Odometer 式迭代。最简单的方法（虽然不是最优雅的）是相应数量的嵌套 for 循环。
所以，我们在这里：
#include <cassert>
#include <iostream>
#include <vector>
enum Op { Add, Sub, Cat, NOps};
int compute(Op op, int l, int r)
{
switch (op) {
case Add: return l + r;
case Sub: return l - r;
case Cat: return l * 10 + r;
}
// ...unreachable for the humans eyes but not for the compiler...
assert(false); return 0;
}
/* Attention!
* cat() must have higher precedence then add() and sub()
*/
int compute(std::vector<int> args, std::vector<Op> &ops)
{
assert(args.size() == ops.size() + 1);
// perform cat()
std::vector<int> args2;
args2.push_back(args[0]);
for (size_t i = 0, n = ops.size(); i < n; ++i) {
if (ops[i] == Cat) {
int l = args2.back(); args2.pop_back();
args2.push_back(compute(Cat, l, args[i + 1]));
} else args2.push_back(args[i + 1]);
}
// perform add() and sub()
int result = args2[0];
for (size_t i = 0, j = 1, n = ops.size(); i < n; ++i) {
const Op op = ops[i];
if (op != Cat) result = compute(op, result, args2[j++]);
}
return result;
}
const char* toString(Op op)
{
static const char* texts[] = { " + ", " - ", "" };
return texts[op];
}
int main()
{
std::vector<int> args = { 1, 2, 3, 4 };
std::vector<Op> ops(args.size() - 1);
for (int op2 = 0; op2 < NOps; ++op2) {
ops[2] = (Op)op2;
for (int op1 = 0; op1 < NOps; ++op1) {
ops[1] = (Op)op1;
for (int op0 = 0; op0 < NOps; ++op0) {
ops[0] = (Op)op0;
// print equation
std::cout << args[0];
for (size_t i = 0, n = ops.size(); i < n; ++i) {
std::cout << toString(ops[i]) << args[i + 1];
}
std::cout << " = " << compute(args, ops) << '\n';
}
}
}
}
输出：
1 + 2 + 3 + 4 = 10
1 - 2 + 3 + 4 = 6
12 + 3 + 4 = 19
1 + 2 - 3 + 4 = 4
1 - 2 - 3 + 4 = 0
12 - 3 + 4 = 13
1 + 23 + 4 = 28
1 - 23 + 4 = -18
123 + 4 = 127
1 + 2 + 3 - 4 = 2
1 - 2 + 3 - 4 = -2
12 + 3 - 4 = 11
1 + 2 - 3 - 4 = -4
1 - 2 - 3 - 4 = -8
12 - 3 - 4 = 5
1 + 23 - 4 = 20
1 - 23 - 4 = -26
123 - 4 = 119
1 + 2 + 34 = 37
1 - 2 + 34 = 33
12 + 34 = 46
1 + 2 - 34 = -31
1 - 2 - 34 = -35
12 - 34 = -22
1 + 234 = 235
1 - 234 = -233
1234 = 1234
注：
我只使用了 4 位数字而不是 9 位数字，因为我相信这足以说明原理并且应该足够容易由 OP 扩展（以及添加计算结果是否可接受的测试).
我有一个练习，找出 1-9 的所有可能总和，加起来等于 100，规则是每个数字必须按顺序使用一次，允许的运算符是 +/- 并添加数字在一起，例如。 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100
我已经写出了解决这个问题的逻辑，我有一个包含 9 个元素的数组，代表可以放置运算符的所有位置，1 个是 +，2 个是 -，3 个是数字相加. 上述示例的运算符字符串为 {1,1,1,2,1,1,1,3,1}.
所以我真正的问题是如何遍历这个运算符数组并生成每个可能的数字组合。
所以我从 {1,1,1,1,1,1,1,1,1}
然后像这样前进，直到数组全是 3
111111111
111111112
111111113
111111121
111111122
111111123
111111131
我在去年左右为此编写了一个函数，但它使用了很多 if else 语句，使该函数不灵活，我想就执行此操作的正确步骤提出建议，因为我想改进我的编码。
OP 非常公正地指出问题是关于家庭作业的
I have a exercise finding all of the possible sums of 1-9 that add up to 100
因此，我没有提供此练习的完整解决方案，而是提供了一些不需要添加太多内容即可实现的解决方案。
给出了九个参数（数字 1 … 9），它们是二元运算符的参数。
二元运算符需要一个左右参数。因此，我得出结论，有 8 个位置可以选择二元运算符。
这对于 + 和 - 来说很容易，但是 添加数字 呢？
这是一个我称之为“连接”的操作。实际上，将“连接”表示为简单的算术表达式很容易：
lr: 10 * l + r
“串联”问题解决后，就没那么复杂了
我的第一个想法是使用仿函数或函数指针之类的东西，但没有它也不难解决。
为此，我定义了一个操作枚举：
enum Op { Add, Sub, Cat, NOps};
和用于这些操作的 compute() 函数：
int compute(Op op, int l, int r)
{
switch (op) {
case Add: return l + r;
case Sub: return l - r;
case Cat: return l * 10 + r;
}
// ...unreachable for the humans eyes but not for the compiler...
assert(false); return 0;
}
下一个拼图是计算完整方程结果的函数。 该等式由 N 个参数（数字）和 N - 1 个运算符定义。
在执行此操作时，我意识到“串联”必须具有更高的优先级。否则，计算功能将无法正常工作。
示例：
12 + 23 = 35
如果不考虑“连接”的更高优先级，这将导致：
12 + 23 = ((12) + 2)3 = (14)3 = 143
对于这个问题的简单解决方案，计算函数应该运行两次：
- 解析所有连接
- 解决所有其他操作。
int compute(std::vector<int> args, std::vector<Op> &ops)
{
assert(args.size() == ops.size() + 1);
// perform cat()
std::vector<int> args2;
args2.push_back(args[0]);
for (size_t i = 0, n = ops.size(); i < n; ++i) {
if (ops[i] == Cat) {
int l = args2.back(); args2.pop_back();
args2.push_back(compute(Cat, l, args[i + 1]));
} else args2.push_back(args[i + 1]);
}
// perform add() and sub()
int result = args2[0];
for (size_t i = 0, j = 1, n = ops.size(); i < n; ++i) {
const Op op = ops[i];
if (op != Cat) result = compute(op, result, args2[j++]);
}
return result;
}
最后缺失的部分是 std::vector<Op> &ops 中值的 Odometer 式迭代。最简单的方法（虽然不是最优雅的）是相应数量的嵌套 for 循环。
所以，我们在这里：
#include <cassert>
#include <iostream>
#include <vector>
enum Op { Add, Sub, Cat, NOps};
int compute(Op op, int l, int r)
{
switch (op) {
case Add: return l + r;
case Sub: return l - r;
case Cat: return l * 10 + r;
}
// ...unreachable for the humans eyes but not for the compiler...
assert(false); return 0;
}
/* Attention!
* cat() must have higher precedence then add() and sub()
*/
int compute(std::vector<int> args, std::vector<Op> &ops)
{
assert(args.size() == ops.size() + 1);
// perform cat()
std::vector<int> args2;
args2.push_back(args[0]);
for (size_t i = 0, n = ops.size(); i < n; ++i) {
if (ops[i] == Cat) {
int l = args2.back(); args2.pop_back();
args2.push_back(compute(Cat, l, args[i + 1]));
} else args2.push_back(args[i + 1]);
}
// perform add() and sub()
int result = args2[0];
for (size_t i = 0, j = 1, n = ops.size(); i < n; ++i) {
const Op op = ops[i];
if (op != Cat) result = compute(op, result, args2[j++]);
}
return result;
}
const char* toString(Op op)
{
static const char* texts[] = { " + ", " - ", "" };
return texts[op];
}
int main()
{
std::vector<int> args = { 1, 2, 3, 4 };
std::vector<Op> ops(args.size() - 1);
for (int op2 = 0; op2 < NOps; ++op2) {
ops[2] = (Op)op2;
for (int op1 = 0; op1 < NOps; ++op1) {
ops[1] = (Op)op1;
for (int op0 = 0; op0 < NOps; ++op0) {
ops[0] = (Op)op0;
// print equation
std::cout << args[0];
for (size_t i = 0, n = ops.size(); i < n; ++i) {
std::cout << toString(ops[i]) << args[i + 1];
}
std::cout << " = " << compute(args, ops) << '\n';
}
}
}
}
输出：
1 + 2 + 3 + 4 = 10
1 - 2 + 3 + 4 = 6
12 + 3 + 4 = 19
1 + 2 - 3 + 4 = 4
1 - 2 - 3 + 4 = 0
12 - 3 + 4 = 13
1 + 23 + 4 = 28
1 - 23 + 4 = -18
123 + 4 = 127
1 + 2 + 3 - 4 = 2
1 - 2 + 3 - 4 = -2
12 + 3 - 4 = 11
1 + 2 - 3 - 4 = -4
1 - 2 - 3 - 4 = -8
12 - 3 - 4 = 5
1 + 23 - 4 = 20
1 - 23 - 4 = -26
123 - 4 = 119
1 + 2 + 34 = 37
1 - 2 + 34 = 33
12 + 34 = 46
1 + 2 - 34 = -31
1 - 2 - 34 = -35
12 - 34 = -22
1 + 234 = 235
1 - 234 = -233
1234 = 1234
注：
我只使用了 4 位数字而不是 9 位数字，因为我相信这足以说明原理并且应该足够容易由 OP 扩展（以及添加计算结果是否可接受的测试).