c++ - 通过重复指定长度的条目生成有序选择

Question

我正在编写一种模仿 sage combinatorial functions 中的 unordered_tuple 的函数在 python 中可用。

不过，它的不同之处在于，我使用的输入集始终是 [10, 9, 8, 7, 6]，只是条目数不同(不大于 10)。

因此，entry = 3 和 entry = 4 所需的输出是，

unordered_tuples([10,9,8,7,6], 3)
[[6, 6, 6],
 [6, 6, 7],
 [6, 6, 8],
 [6, 6, 9],
 [6, 6, 10],
 [6, 7, 7],
 [6, 7, 8],
 [6, 7, 9],
 [6, 7, 10],
 [6, 8, 8],
 [6, 8, 9],
 [6, 8, 10],
 [6, 9, 9],
 [6, 9, 10],
 [6, 10, 10],
 [7, 7, 7],
 [7, 7, 8],
 [7, 7, 9],
 [7, 7, 10],
 [7, 8, 8],
 [7, 8, 9],
 [7, 8, 10],
 [7, 9, 9],
 [7, 9, 10],
 [7, 10, 10],
 [8, 8, 8],
 [8, 8, 9],
 [8, 8, 10],
 [8, 9, 9],
 [8, 9, 10],
 [8, 10, 10],
 [9, 9, 9],
 [9, 9, 10],
 [9, 10, 10],
 [10, 10, 10]]

unordered_tuples([10,9,8,7,6], 4)
[[6, 6, 6, 6],
 [6, 6, 6, 7],
 [6, 6, 6, 8],
 [6, 6, 6, 9],
 [6, 6, 6, 10],
 [6, 6, 7, 7],
 [6, 6, 7, 8],
 [6, 6, 7, 9],
 [6, 6, 7, 10],
 [6, 6, 8, 8],
 [6, 6, 8, 9],
 [6, 6, 8, 10],
 [6, 6, 9, 9],
 [6, 6, 9, 10],
 [6, 6, 10, 10],
 [6, 7, 7, 7],
 [6, 7, 7, 8],
 [6, 7, 7, 9],
 [6, 7, 7, 10],
 [6, 7, 8, 8],
 [6, 7, 8, 9],
 [6, 7, 8, 10],
 [6, 7, 9, 9],
 [6, 7, 9, 10],
 [6, 7, 10, 10],
 [6, 8, 8, 8],
 [6, 8, 8, 9],
 [6, 8, 8, 10],
 [6, 8, 9, 9],
 [6, 8, 9, 10],
 [6, 8, 10, 10],
 [6, 9, 9, 9],
 [6, 9, 9, 10],
 [6, 9, 10, 10],
 [6, 10, 10, 10],
 [7, 7, 7, 7],
 [7, 7, 7, 8],
 [7, 7, 7, 9],
 [7, 7, 7, 10],
 [7, 7, 8, 8],
 [7, 7, 8, 9],
 [7, 7, 8, 10],
 [7, 7, 9, 9],
 [7, 7, 9, 10],
 [7, 7, 10, 10],
 [7, 8, 8, 8],
 [7, 8, 8, 9],
 [7, 8, 8, 10],
 [7, 8, 9, 9],
 [7, 8, 9, 10],
 [7, 8, 10, 10],
 [7, 9, 9, 9],
 [7, 9, 9, 10],
 [7, 9, 10, 10],
 [7, 10, 10, 10],
 [8, 8, 8, 8],
 [8, 8, 8, 9],
 [8, 8, 8, 10],
 [8, 8, 9, 9],
 [8, 8, 9, 10],
 [8, 8, 10, 10],
 [8, 9, 9, 9],
 [8, 9, 9, 10],
 [8, 9, 10, 10],
 [8, 10, 10, 10],
 [9, 9, 9, 9],
 [9, 9, 9, 10],
 [9, 9, 10, 10],
 [9, 10, 10, 10],
 [10, 10, 10, 10]]

然后是我编写的 c++ 函数。

我其实不是一个经验丰富的程序员，我只是试图想出正确的解决方案，但它工作正常，但它给出了很多重复的解决方案。

老实说，我写了这个函数，但我什至不知道我写了什么。

我可以使用 set，但效率很低，我想知道这个问题的正确解决方案。

任何人都可以修复它以提供上面的输出吗？

    #include<iostream>
    #include<string>
    #include<cstdlib>
    #include<vector>

    using namespace std;

    vector<vector<int> > ut(int);

    int main(int argc, char** argv) {
        int entry = atoi(argv[1]);
        ut(entry);
        return 1;
    }

    vector<vector<int> > ut(int entry) {
        vector<vector<int> > ret;

        int upper = 10;
        vector<int> v(entry, upper);
        ret.push_back(v);

        typedef vector<int>::iterator iter_t;

        iter_t it = v.begin();
        int count=0;
        int c = 0;
        while(v.back() != 6) {
            v = ret[count+c];
            while(it != v.end()) {
                --(*it);
                ++it;
                ret.push_back(v);
                ++c;
            }
            it = v.begin();
            c=0;
            ++count;
        }


        for(int i=0; i<ret.size(); ++i) {
            vector<int> tuple = ret[i];
            for(int j=0; j<tuple.size(); ++j) {
                cout << tuple[j] << ' ';
            }
            cout<<endl;
        }
        cout << endl;
        return ret;
    }

Answer 1

看这里:

vector<vector<int> > ret;

int upper = 10;
vector<int> v(entry, upper);
ret.push_back(v);

typedef vector<int>::iterator iter_t;

iter_t it = v.begin();
int count=0;
int c = 0;
while(v.back() != 6) {
  v = ret[count+c];
  while(it != v.end()) {
    --(*it);
    ++it;
    ret.push_back(v);
    ++c;
  }
  it = v.begin();
  c=0;
  ++count;
}

这只是可怕。 (我知道你是初学者；请理解我的批评是为了提供帮助。)通常这种密集的复杂性是不必要的，并且可以作为 bug 的藏身之处。请注意，c 和 it 是在循环之前和循环结束时设置的，并且不再使用;我们可以将它们设置在循环的开头，这样代码会更短更清晰:

int count=0;
while(v.back() != 6) {
  iter_t it = v.begin();
  int c = 0;
  v = ret[count+c];
  while(it != v.end()) {
    --(*it);
    ++it;
    ret.push_back(v);
    ++c;
  }
  ++count;
}

现在我们可以看到 c 除非为零，否则从不使用。 (如果你不相信我，请查看原始代码。)但更糟糕的是，it 指向 v，然后是 v被分配了一个新值。所以 it 可能指向死内存，取消引用它会导致未定义的行为。并且不清楚这段代码是如何工作的。

试试这个:

vector<int> v(n,6);

vector<int>::iterator itr1;
do{
  ret.push_back(v);

  itr1 = v.begin();

  while(++(*itr1)>10){
      if(++itr1==v.end())
        break;
  }
  for(vector<int>::iterator itr2 = v.begin(); itr2!=itr1; ++itr2)
    *itr2 = *itr1;
}
while(itr1!=v.end());