获取给定模型的所有构建订单。

Question

我有问题。我需要为我的工作，一些组件的所有可能的构建顺序。举个简单的例子，你可以想象一个简单的乐高金字塔：

http://i.stack.imgur.com/Y7Lcr.jpg

我尝试了一些DFS，但没有效果。在结尾有一些遗漏的可能性。

有人能帮我吗？语言应该是C++，但我只需要一个提示，而不是一个完整的算法。

一些信息:这些模型以XML文件的形式提供。在那里，您可以找到所有3个方向(x，y，z)的所有邻域关系。所有部件都有唯一的名称/id。开头未定义。在构建顺序上没有限制。因此，你不必完成金字塔的一层，就可以开始另一层。我知道有很多可能的构建顺序。即使是3x3-base本身也有很多可能性(9个阶乘)。但目前这并不重要。

求求你我需要帮助。

你好，埃里克

Answer 1

首先，将每一层(或“课程”)视为一个独立的问题。考虑一下底部的9块砖；忽略所有其他的，有9块！可能的订单，所以生成这些订单，称为P。4也是如此！中间砖的可能订单是Q。我们现在可以忽略顶部的单块积木。

在P和Q上迭代。给定底部砖p和中间砖q的顺序，在底部完成之前，q的第一个移动(即，铺设第一个中间砖)可能是可能的，因此我们可以将该移动与p的移动一起散布；对于q<代码>E217的第一个允许时间，迭代第二个<代码>E118Q<代码>E219的允许时间，并对它们中的每个迭代第三个允许的时间，依此类推。

请注意，顶部的砖块必须始终放在最后。这也是件好事。

这足够继续下去了吗？

Answer 2

如果对放置的顺序没有任何限制，那么可以放置的块的顺序就完全不同了( n! different permutations )。在这种情况下，一个简单的解决方案是将所有的块(或者更确切地说，它们的id)放入一个向量中，并使用std::next_permutation生成所有的排列。