いくつかの条件ですべての可能な行列を生成するプログラムを作成しました。
引数 'r' と 'n' を取ります。ここで、'r' は行列の行または列の数であり、'n' は各行または列の合計の最大数です。
条件は次のとおりです。
- 各行と各列のすべてのエントリは昇順ではありません
- 各行と各列の合計は「n」以下である必要があります
- 主対角線のエントリは非昇順です (すべての i>j に対して m[i][i] >= m[j][j])。
また、条件を満たすすべての可能性を生成する必要があります。
したがって、私のアプローチは、最初に 0 番目の行と列を生成し、次に 1 番目の行と列というように、'r' 番目の行と列に到達するまで生成していました。
forループを使用して左上のエントリを繰り返し設定し、その左上のエントリでgenWat関数を呼び出して、Boostライブラリを使用してすべての可能な行エントリと列エントリを生成し、置換と組み合わせてこれを行いました.( http://photon.poly. edu/~hbr/boost/combination.hpp )
次に、条件をチェックし、生成されたエントリが条件に適合する (テストに合格する) 場合、それらは行列 (Wat クラスの m) に格納され、次の行と列 (私はそれを「ターゲット」と呼びます。例えば、2 行目と 2 列目を扱う場合、ターゲットは 2) 左上のエントリを繰り返し設定し、それらの左上のエントリで genWat 関数を再帰的に呼び出すことです。
r番目の行と列(target == 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;
}