python中的排列,有一个扭曲

我有一个对象列表(例如,让我们说5).我想要一些可能的排列列表.具体来说,鉴于有些对不在一起,而有些三元组不能制作三明治,我怎样才能产生所有其他排列？我意识到我首先生成所有这些并检查它们是否有效,但我认为甚至不考虑不起作用的对和三元组会更快.

我错了,先检查并稍后生成会更快吗？

我该怎么办？

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

编辑:
示例:在集合(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   |     |   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个排列,所以如果检查限制(而不是构建列表)是瓶颈,我们最好还是构建所有排列并在最后检查它们......如果我们走这条路时检查无法优化.

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

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

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

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

嗯.对不起,我进入了演讲模式; 忍受我.