3

私が達成しようとしていることの名前や方法は確かにありますが、この質問のやや漠然としたタイトルから判断できるように、私はそれをどのように表現するかわからないため、検索に問題があります。

これが私がやりたいことです：

いくつかの可能な状態のアイテムのリストがあります。簡単にするために、アイテムA、B、C、および状態を0から5と呼びましょう。

各アイテムの状態は、各ステップで1ずつしかインクリメントできません。各ステップでインクリメントできるアイテムは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

0Five 、 Five 1、Five を使用して、長さが 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の場合は、二項係数と考えることができます。左下または下に移動せずに、左下から右上に移動しようとしている長方形を想像してください。パスカルの三角形を介してカウントを実装できます。これがウィキペディアの写真です。

パスカルの三角形

実際、これはパスカルのシンプレックスを使用する多項定理に一般化されます。

これは再帰的に（擬似コードで）解決できます。

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 に答える