如何编写c++代码来重新排列单词顺序，使每个单词的第一个字母(第一个除外)等于前一个单词的最后一个字母?
注意:这个问题听起来很具体，没有什么实用价值。然而，它很容易解释和理解，解决它所需的技术可以应用于几个问题，这些问题需要找到一个完整的路径，通过一个模型约束或障碍的图来访问每个"节点"一次。这些问题可能非常难以理解，但一旦知道了生成树和深度优先搜索的技术，就可以直接解决这些问题。有关使用相同方法解决几个现实世界问题的代码，请参阅https://github.com/JamesBremner/obstacles
细节:
输入一个单词列表，每行一个单词，所有字母小写a到z
输出一个有序的单词列表，使得除第一个单词外，每个单词的第一个字母等于前一个单词的最后一个字母。列表中的所有单词都必须使用，每个单词都必须使用一次。被提到过几次的单词必须重复几次。
算法:
-
通过连接首尾字母匹配的单词(例如abc ->cde)
-
在图中找到一个生成树。(如果找不到生成树，则不能按指定的顺序排列单词)
-
LOOP N over words
-
从N
开始对生成树进行深度优先搜索 -
如果搜索到每个单词
- 按到达的顺序输出单词。
-
该算法通常很有用，可以应用于障碍物周围的路线规划问题(例如https://github.com/JamesBremner/obstacles)
下面是实现算法的代码:#include <string>
#include <fstream>
#include <sstream>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
class cGraph;
/// @brief Spanning tree
class cTree
{
cGraph &myGraph;
/// @brief links in spanning tree
std::vector<std::pair<int, int>> myLink;
std::vector<bool> myVisited;
/// @brief links arranged so last matched next first
std::vector<std::pair<int, int>> myArrange;
public:
cTree(cGraph &g)
: myGraph(g)
{
}
void add(int n1, int n2)
{
myLink.push_back(std::make_pair(n1, n2));
}
int nodeCount();
std::string text();
/// @brief Depth first search starting at a link
/// @param link
/// @return true if every word was reached
bool dfs(
const std::pair<int, int> &link);
/// @brief arrange words into required order
///
/// The last letter of each word must be the
/// same as the first letter of the next word
std::vector<std::pair<int, int>> arrange();
};
class cGraph
{
std::vector<std::string> myWord;
std::vector<std::vector<bool>> myAdj;
std::vector<std::pair<int, int>> myArrange;
public:
void setSize(int s)
{
myAdj.resize(s, std::vector<bool>(s, false));
}
void addLink(int n1, int n2)
{
myAdj[n1][n2] = true;
}
void read(const std::string &fname);
void constructAdjacencyMatrix();
int wordCount() const
{
return myWord.size();
}
std::string word(int idx) const
{
return myWord[idx];
}
std::vector<int> sources(int n);
std::vector<int> targets(int n);
void arrange();
void displayArrange();
private:
cTree spanningTree();
};
int cTree::nodeCount()
{
std::set<int> nodes;
for (auto &l : myLink)
{
nodes.insert(l.first);
nodes.insert(l.second);
}
return nodes.size();
}
std::string cTree::text()
{
std::stringstream ss;
for (auto &l : myLink)
ss << myGraph.word(l.first)
<< " -> "
<< myGraph.word(l.second)
<< " ";
return ss.str();
}
std::vector<int> cGraph::sources(int n)
{
std::vector<int> ret;
int n1idx = -1;
for (auto &vl : myAdj)
{
n1idx++;
int n2idx = -1;
for (bool l : vl)
{
n2idx++;
if (n2idx == n)
if (l)
ret.push_back(n1idx);
}
}
return ret;
}
std::vector<int> cGraph::targets(int n)
{
std::vector<int> ret;
int n2idx = -1;
for (bool l : myAdj[n])
{
n2idx++;
if (l)
ret.push_back(n2idx);
}
return ret;
}
cTree cGraph::spanningTree()
{
cTree mySpanningTree(*this);
std::vector<bool> visited(myAdj.size(), false);
// add initial arbitrary link
int v, w;
for (v = 0; v < myAdj.size(); v++)
{
auto vt = targets(v);
if (vt.size())
{
w = vt[0];
mySpanningTree.add(v, w);
break;
}
}
if (v == myAdj.size())
throw std::runtime_error("no links");
visited[v] = true;
visited[w] = true;
// while nodes remain outside of span
bool fdone = false;
while (!fdone)
{
// loop over nodes in span
for (v = 0; v < myAdj.size(); v++)
{
if (!visited[v])
continue;
// loop over nodes not in span
fdone = true;
for (w = 0; w < myAdj.size(); w++)
{
if (visited[w])
continue;
fdone = false;
if (myAdj[v][w])
{
mySpanningTree.add(v, w);
visited[w] = true;
}
if (myAdj[w][v])
{
mySpanningTree.add(w, v);
visited[w] = true;
}
}
}
if (v == myAdj.size())
fdone = true;
}
if (mySpanningTree.nodeCount() < myAdj.size())
throw std::runtime_error(
"Spanning tree incomplete: no solution availablen");
// std::cout << "n"
// << mySpanningTree.text() << "n";
return mySpanningTree;
}
void cGraph::arrange()
{
// Find a spanning tree and search it for a matching word arrangement
// throw exception if no arrangement possible
myArrange = spanningTree().arrange();
}
void cGraph::displayArrange()
{
// display the arrangement found
std::cout << "arrange into "
<< word(myArrange[0].first) << " ";
for (auto &l : myArrange)
std::cout << word(l.second) << " ";
std::cout << "n";
}
void cGraph::read(const std::string &fname)
{
std::ifstream ifs(fname);
if (!ifs.is_open())
{
std::cout << "cannot open inputn";
exit(1);
}
std::string word;
ifs >> word; // skip count
while (ifs.good())
{
ifs >> word;
myWord.push_back(word);
std::cout << word << "n";
}
setSize(myWord.size());
}
void cGraph::constructAdjacencyMatrix()
{
int widx = -1;
for (auto &w : myWord)
{
widx++;
char first = w[0];
char last = w[w.length() - 1];
int sidx = -1;
for (auto &src : myWord)
{
sidx++;
if (sidx == widx)
continue;
if (src[src.length() - 1] == first)
{
addLink(sidx, widx);
}
if (src[0] == last)
{
addLink(widx, sidx);
}
}
}
}
bool cTree::dfs(
const std::pair<int, int> &l)
{
myVisited[l.first] = true;
myVisited[l.second] = true;
bool fdone = true;
for (bool v : myVisited)
{
if (!v)
{
fdone = false;
break;
}
}
if (fdone)
{
myArrange.push_back(l);
return true;
}
auto visited_save = myVisited;
for (const auto &lnext : myLink)
{
if (lnext.first == l.second)
{
myVisited = visited_save;
if (dfs(lnext))
{
myArrange.push_back(l);
return true;
}
}
}
return false;
}
std::vector<std::pair<int, int>> cTree::arrange()
{
// loop over links in spanning tree
for (const auto &l : myLink)
{
// do a depth fist search through the tree
// starting from this link
myVisited.clear();
myVisited.resize(myGraph.wordCount(), false);
if (dfs(l))
{
// the dfs reached every word
// reverse the order in which the words were found
// which gives an arrangement of words in required order
std::reverse(myArrange.begin(), myArrange.end());
// done
return myArrange;
}
}
}
main()
{
cGraph graph;
// read word list from file
graph.read("input.txt");
// connect matching words
graph.constructAdjacencyMatrix();
// arrange words, matching first and last letters
graph.arrange();
// output results
graph.displayArrange();
return 0;
}