python中的排列，带有扭曲

Question

我有一个对象列表（为了举例，比方说5）。我想要列出一些可能的排列组合。具体而言，鉴于有些配对不在一起，有些三元组不能制作三明治，我怎么能产生所有其他排列？我意识到，我首先生成了它们，并检查它们是否正常工作，但我认为即使不考虑不成对的对和三元组也会更快。

我错了，先检查后再生成会更快吗？

我该怎么做？

Answer 1

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

编辑：
实施例：在该组（A B C d），让我们说，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 |  | X  X | | X  X |  | X | X 
    ABDC ACDB BACD   BDCA CABD   CDBA  DBAC DCAB 
    v  v  v    v  v   v  v  v 

没有括号的每个字符串都需要检查。正如你看到的那样，Xs（其中子树已被切断）保存检查，如果它们在第三行，则检查一次，但如果它们在第二行，则检查四次。我们在这里节省了60个支票中的24个，下降到36个。然而，总体上只有24个排列，因此如果检查限制（而不是建立列表）是瓶颈，那么我们最好是构建所有排列并在最后检查它们......如果我们这样做时检查无法优化。

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

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

我们所做的保存是构建列表和峰值内存消耗的时间。建立一个列表通常相当快，但如果对象数量变大，峰值内存消耗可能会成为一个考虑因素。对于第一个构建然后过滤器，两者都随着对象的数量线性增长。对于树版本，它的增长速度较慢，取决于约束条件。从一定数量的对象和规则上，也有实际的检查保存。

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

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