2

文字列があるとしますABCD

次のツリーを作成したいと思います。

     ABCD             <------ level 1
 ABC ABD ACD BCD      <------ level 2
AB AC AD BC BD CD     <------ level 3
    A B C D           <------ level 4

そして、次の順序でベクター内に保存します。

ABCD->ABC->ABD->ACD->BCD->AB->AC->AD->BC->BD->CD->A->B->C->D

したがって、出発点から、次のレベルのノードを生成し、それらをベクトル内に格納してから、次のレベルのノードを生成し、残りのすべてのレベルに対して同じことを行いたいと考えています

レベル 1 からレベル 2 を生成する次のプログラムを作成しました。

void test(int dimensions, vector<string> & nodes, const char* currentNode){

     int i,j;

     for(i=dimensions-1;i>=0;i--){
         char *temp = new char[dimensions];
         int counter = 0;
         for(j=0;j<dimensions;j++){
             if(j!=i){
                temp[counter] = currentNode[j];
                counter++;
             }
          }
          temp[counter] = '\0';
          nodes.push_back(temp);
      }
}

メインから呼び出されます：

vector<string> nodes;
int dimension = 4;
nodes.push_back("ABCD");
test(dimension, nodes, "ABCD");

これにより、次のことがわかります。

ここに画像の説明を入力

ご覧のとおり、レベル 2 のノードは正常に追加されていますが、ここで再帰を適用しようとすると、たとえばノード「ABC」に

私は結果として得ます：

AB -> AC -> BC

これらは正常に保存されますが、再帰が続く場合、たとえばノードのAB今はA -> B

そのため、ベクトルに保存されたノードの結果の順序は、最初に説明した方法とは異なります。

それ以外の

    ABCD->ABC->ABD->ACD->BCD->AB->AC->AD->BC->BD->CD->...

そうなる

ABCD->ABC->ABD->ACD->BCD->AB->AC->A->B->...

最後に、このツリーの計算を任意の数の次元に対して一般化したいと思います。たとえば、最初のノードはABCDまたはABCDEFGHIJKLMです。

何らかの理由で、これを行うのは非常に難しいと思いますが、正確にはわかりません。順列の計算に外部ライブラリを使用したくないことに注意してください。実装したいアルゴリズムを進めるには、コードを 100% 理解する必要があります。

前もって感謝します

4

1 に答える 1

1

コメントに記載されているように、これが順列にどのように関連しているかはわかりませんが、達成しようとしていると思われるコードは次のとおりです。

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

typedef std::vector<std::string> Layer;

Layer getNextLayer(const Layer &);

int main()
{
   std::vector<Layer> layers;
   layers.push_back(Layer());
   layers[0].push_back("ABCDE");
   while ( layers.back().back().size() > 1 )
   {
       layers.push_back(getNextLayer(layers.back()));
       for ( size_t i = 0; i < layers.back().size(); ++i )
       {
          std::cout << layers.back()[i] << " ";
       }
       std::cout << "\n";
   }
}

Layer getNextLayer(const Layer &layer)
{
   Layer result;
   for ( size_t i = 0; i < layer.size(); ++i )
   {
      const std::string item = layer[i];
      for ( size_t j = 0; j < item.size(); ++j )
      {
         std::string new_item = item;
         new_item.erase(new_item.begin() + j); // erase j^th charachter from item
         result.push_back(new_item);
      }
   }
   std::sort(result.begin(), result.end());
   result.erase(std::unique(result.begin(), result.end()), result.end()); // erase duplicates
   return result;     
}

これにより、最後のレイヤーに基づいて各レイヤーが作成されます。すべてを 1 つのベクトルに格納するには、これらすべてのレイヤーを結合するだけです。

于 2013-03-04T17:11:10.267 に答える