问python中的排列，有一个扭曲？

EN

您必须找到一种算法，在单次检查后切断多个不需要的排列，以获得任何收益。显而易见的策略是按顺序构建排列，例如，在树中。然后每次切割消除整个分支。

编辑： 示例：在集合（ABCD）中，假设B和C以及A​​和D不允许是邻居。

       （A B C D）
     /  |  \            /  |  \            /  |  \            /  |  \
 AB AC AD BA BC BD CA CB CD DA DB DC
 | \ | \ X / \ X / \ / \ X / \ X / \ / \
ABC ABD ACB ACD BAC BAD BDA BDC CAB CAD CDA CDB DBA DBC DCA DCB
 X | X | | XX | | XX | | X | X
    USC ACDB BACD BDCA CABD CDBA DBAC DCAB
     vvvvvvvv

没有括号的每个字符串都需要检查。如您所见，Xs（其中子树已被切断）保存检查，如果它们在第三行，则为一，如果它们在第二行，则为四。我们在这里保存了60个检查中的24个并且降到了36个。然而，总体上只有24个排列，所以如果检查限制（而不是构建列表）是瓶颈，我们最好还是构建所有排列并在最后检查它们......如果我们走这条路时检查无法优化。

现在，如您所见，只需要在每个列表的新部分执行检查。这使得支票更加精简; 实际上，我们将完全排列所需的检查分成小块。在上面的例子中，我们只需要查看添加的字母是否允许在最后一个字母之外，而不是之前的所有字母。

但是，如果我们首先构造，然后过滤，一旦遇到禁止，就可以缩短检查时间。因此，在检查时，与首次构建然后过滤器算法相比，没有真正的增益; 通过更多的函数调用存在进一步开销的危险。

我们节省的是构建列表的时间和峰值内存消耗。构建列表通常相当快，但如果对象的数量变大，则可能需要考虑峰值内存消耗。对于first-build-then-filter，它们都随着对象的数量线性增长。对于树版本，它会变慢，具体取决于约束。从一定数量的对象和规则开始，还有实际的检查保存。

一般来说，我认为您需要尝试并计算两种算法的时间。如果你真的只有5个物体，坚持简单(filter rules (build-permutations set))。如果你的对象数量变大，树算法在某些时候会表现得更好（你知道，大O）。

嗯。对不起，我进入了演讲模式; 忍受我。