我编写了一个程序来生成具有某些条件的所有可能的矩阵。
它接受参数“r”和“n”，其中“r”是矩阵中的行数或列数，“n”是每行或每列中的和可以是的最大数
条件是：
- 每行和每列中的所有条目都按非升序排列
- 每行每列的总和应小于或等于'n'
- 主对角线中的条目按非升序排列（对于所有 i>j，m[i][i] >= m[j][j]）
它还必须产生满足条件的所有可能性。
所以，我的方法是先生成第 0 行和第 0 列，然后是第 1 行和第 1 列，依此类推，直到我达到第 'r' 行和第列。
我通过使用 for 循环迭代地设置左上条目并使用该左上条目调用 genWat 函数来做到这一点，以使用 Boost 库生成所有可能的行条目和列条目以与替换相结合。（http://photon.poly. edu/~hbr/boost/combination.hpp）
然后它检查条件，如果生成的条目符合条件（通过测试），它们将存储在矩阵中（Wat 类中的 m），并再次存储在下一行和下一列中（我称之为“目标”。例如，如果它正在处理第 2 行和第 2 列，则目标是 2) 迭代设置左上条目并使用这些左上条目递归调用 genWat 函数。
它一直持续到它生成第 r 行和第 r 列（目标 == r），如果第 r 行和第 r 列满足条件，它将那个 Wat 存储到 Wat 的向量中。
这可能是我写过的最复杂的程序，主要是因为它同时使用递归和迭代，我发现这个问题很有趣，但我无法让它工作，不得不寻求帮助。
它可以编译，但是当我用一些小的 r 和 n 值（例如 2 和 4）运行程序时，它会一直运行下去。对于 r=1，它会抛出 out_of_bounds 异常。
我认为递归并没有退出，因为递归的基本情况没有很好地定义，但我不知道为什么程序不工作。
诚然，代码很混乱，冗长而复杂，但请帮我弄清楚如何解决这个问题。
谢谢你。
#include<iostream>
#include<vector>
#include<string>
#include<stdlib.h>
#include<algorithm>
#include"combination.hpp"
using namespace std;
class Wat {
public:
int r, n;
vector<vector<int> > m;
vector<int> sumRow;
vector<int> sumCol;
Wat(const int r, const int n)
: r(r), n(n)
m(vector<vector<int> > (r, vector<int> (r, 0))),
sumRow(vector<int> (r, 0)),
sumCol(vector<int> (r, 0)) { }
~Wat() {
//delete m;
//delete sumRow;
//delete sumCol;
}
Wat(const Wat& source) {
r=source.r;
n=source.n;
m = source.m;
sumRow = source.sumRow;
sumCol = source.sumCol;
}
Wat operator=(const Wat& rhs) {
Wat tmp(rhs);
std::swap(r, tmp.r);
std::swap(n, tmp.n);
std::swap(m, tmp.m);
std::swap(sumRow, tmp.sumRow);
std::swap(sumCol, tmp.sumCol);
}
void index_assign(int row, int col, int item) {
(m.at(row)).assign(col, item);
sumRow[row] += item;
sumCol[col] += item;
}
void row_assign(int row, int startColIdx, vector<int> items) {
for(int i = 0; i < items.size(); ++i) {
index_assign(row, startColIdx + i, items.at(i));
}
}
void col_assign(int startRowIdx, int col, vector<int> items) {
for(int i = 0; i < items.size(); ++i) {
index_assign(startRowIdx + i, col, items.at(i));
}
}
bool checkSumForRow(int target, const vector<int>& gen_row) const {
bool ret = true;
int testedSum = sumRow[target];
for (int i=0; i<gen_row.size(); ++i) {
if(sumCol[target+1+i] + gen_row[i] > n) {
ret = false;
}
testedSum += gen_row[i];
}
if (testedSum > n) {
ret = false;
}
return ret;
}
bool checkSumForCol(int target, const vector<int>& gen_col) const {
bool ret = true;
int testedSum = sumCol[target];
for (int i=0; i<gen_col.size(); ++i) {
if(sumRow[target+1+i] + gen_col[i] > n) {
ret = false;
}
testedSum += gen_col[i];
}
if (testedSum > n) {
ret = false;
}
return ret;
}
};
bool isNonAscending (const vector<int>& v);
void genWat(const Wat& w, int target, int r, int n, vector<Wat>& vw);
int main(int argc, char** argv) {
if(argc != 3) {
cerr << "arguments: r and n" << endl;
return 0;
}
else {
vector<Wat> v;
int r = atoi(argv[1]);
int n = atoi(argv[2]);
Wat waat(r, n); //starts from empty Wat, make a copy of previous Wat if needed, and add to v when complete
for (int i = 0; i < n; ++i) {
waat.index_assign(0, 0, i);
genWat(waat, 0, r, n, v);
}
return 1;
}
}
void genWat(const Wat& w, int target, int r, int n, vector<Wat>& vw) {
if(target == r) {
//compare the entries on each side beside diagonal first
vw.push_back(w);
}
else if(target == r+1) {//might be the base case?? {
return;
}
else {
std::vector<int> gen_row(r-1, 0);
do {
if (isNonAscending(gen_row)) {
//need to define assignment operator, but actually to make it efficient, no need to make a copy here(just make a copy of sumRow and sumCol, and check the sum)
if (w.checkSumForRow(target, gen_row)) {
std::vector<int> gen_col(r-1, 0);
do {
if(isNonAscending(gen_col)) {
if(w.checkSumForCol(target, gen_col)) {
Wat waaat = w;
waaat.row_assign(target, target+1, gen_row);
waaat.col_assign(target+1, target, gen_col);
int leftTopBound = min((waaat.m)[target][target], waaat.n - max(waaat.sumRow[target+1], waaat.sumCol[target+1]));
for (int i = 0; i < leftTopBound; ++i) {
waaat.index_assign(target+1, target+1, i);
genWat(waaat, target+1, r, n, vw);
}
}
}
} while (boost::next_mapping(gen_col.begin(), gen_col.end(), 0, w.m[target][target]));
}
}
} while (boost::next_mapping(gen_row.begin(), gen_row.end(), 0, w.m[target][target]));
}
}
bool isNonAscending (const vector<int>& v) {
for(int i=0; i < v.size()-1; ++i) {
if(v.at(i) < v.at(i+1)) {
return false;
}
}
return true;
}