3

我确信我想要实现的目标有一个名称或方法，但正如您可以从这个问题的有点模糊的标题中判断的那样，我只是不知道如何措辞，因此在搜索时遇到了麻烦。

这是我想做的事情：

我有一个包含几种可能状态的项目列表。为简单起见，我们称项目 A、B 和 C 以及状态 0 到 5。

每个项目的状态在每个步骤中只能增加 1。每一步只能增加一项。在每个场景 A 开始时，B 和 C 都是 0。在每个场景 A 结束时，B 和 C 都是 5。

这将是最明显场景的一个示例。所有场景都将具有相同数量的步骤。

A 0 1 2 3 4 5 5 5 5 5 5 5 5 5 5 5 
B 0 0 0 0 0 0 1 2 3 4 5 5 5 5 5 5 
C 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5

我想遍历每一个可能的“决策路径”。我在每一步都有计算要执行，我有每个场景的值要比较以确定哪个更好。以防万一还不清楚，这是一个完全随机场景的示例，但最终将使用所需的算法运行。

A 0 0 0 0 0 0 1 1 2 3 4 5 5 5 5 5
B 0 1 2 2 3 3 3 4 4 4 4 4 4 4 5 5
C 0 0 0 1 1 2 2 2 2 2 2 2 3 4 4 5

这类任务有名称或通用程序吗？不一定要寻找直接答案（将是一个奖励），但至少需要一些关键词，这样我才能更有效地搜索！

提前致谢。

4

2 回答 2

2

0用 5 、 51和 5枚举所有可能的长度为 15 的单词2。 0表示增加A,1表示增加B,2表示增加C.

#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
int main(){
  int n=5;
  vector<int> u(3),v(3*n);
  for (int i = 0; i < n; i++){
    v[i] = 0; v[i+n] = 1; v[i+2*n] = 2;
  }
  do
  {
    fill(u.begin(),u.end(),0);
    for (int j = 0; j < 3*n; j++){
      for (int i = 0; i < 3; i++)
        cout << u[i] << "\t";
      cout << endl;
      u[v[j]]++;
    }
    for (int i = 0; i < 3; i++)
      cout << u[i] << "\t";
    cout << endl;
    cout << endl;
  } while (next_permutation(v.begin(),v.end()));
  return 0;
}
于 2012-10-19T04:15:11.277 回答
1

您可以将 2D 案例视为二项式系数 - 想象一个矩形，您试图从左下角到右上角而不向左或向下。您可以通过Pascal's triangle实现计数。这是一张来自维基百科的图片：

帕斯卡三角

事实上，这可以推广到使用Pascal 单纯形的多项式。

您可以递归地解决这个问题（在伪代码中）：

go( a: List, list: List ) = {
  if (a.forall(_ == 0)) {
    // do magic on list
  } else {
    a.zip(1 to a.size).foreach( (number,index) => if (number > 0 ) {
      go(a.patch(index-1,Seq(number-1),1), list ++ index)
    })
  }
}
于 2012-10-19T09:14:57.270 回答