python中的排列,有一个扭曲?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (1)
  • 关注 (0)
  • 查看 (49)

我有一个对象列表(例如,让我们说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 | | 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)。

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

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励