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);
      }
}

从 main 调用：

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

这给了我以下信息：

在此处输入图像描述

如您所见，级别 2 的节点已成功添加，但是如果我尝试在此处应用递归，例如节点“ABC”

结果我会得到：

AB -> AC -> BC

这些将成功保存，但是如果递归继续进行，例如对于 node ABnow 它会找到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;     
}

这将基于最后一层创建每一层。要将其全部存储在一个向量中，您只需合并所有这些层。

于 2013-03-04T17:11:10.267 回答