-4

我编写了一个程序来生成具有某些条件的所有可能的矩阵。

它接受参数“r”和“n”,其中“r”是矩阵中的行数或列数,“n”是每行或每列中的和可以是的最大数

条件是:

  1. 每行和每列中的所有条目都按非升序排列
  2. 每行每列的总和应小于或等于'n'
  3. 主对角线中的条目按非升序排列(对于所有 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;
    }
4

2 回答 2

2

首先,请注意:您的代码存在很多问题。建议您以易于人们帮助的方式发布问题。您的代码不会像发布的那样编译,需要使用第三方头文件。您的析构函数和构造函数都有错误。无论如何,关于rn都等于的情况1,下面这行就是问题所在:

std::vector<int> gen_row(r-1, 0);

这在函数内部调用genWat。使用r等于1,您正在尝试制作一个大小为 的向量0。就其本身而言,这不一定是个问题。但是随后您调用isNonAscending并尝试检查第 0 个索引 - 但第 0 个索引不存在,因为向量的大小为 0!

在尝试修复无限循环问题之前,我将专注于修复最简单情况 (r = 1和) 的崩溃。n = 1

编辑:对于有兴趣查看的其他人,以下代码在 VS2010 上为我编译,我相信它遵循原始代码的精神。您显然还需要combination.hpp从问题中给出的链接下载。

#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(r), sumRow(r), sumCol(r) { }

  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;
}
于 2013-06-12T15:20:15.147 回答
0

当您的 first_value 和 last_value 相同时,您提供的似乎combination.hpp不喜欢。你告诉它生成从 0 到 0 的所有组合并且它永远不会停止。我将第 269 行从:

     if (++(*(--last)) != last_value)

     if (++(*(--last)) < last_value)

并且代码不再无限长地运行。

这不是一个适当的修复!我不知道组合是否仍然正确生成next_mapping并决定从这里留给你。

高温高压

于 2013-06-12T15:29:34.920 回答