我有一个对象列表(例如,让我们说5)。我想要一些可能的排列列表。具体来说,鉴于有些对不在一起,而有些三元组不能制作三明治,我怎样才能产生所有其他排列?我意识到我首先生成所有这些并检查它们是否有效,但我认为甚至不考虑不起作用的对和三元组会更快。
我错了,先检查并稍后生成会更快吗?
我该怎么办?
发布于 2018-10-12 09:57:07
您必须找到一种算法,在单次检查后切断多个不需要的排列,以获得任何收益。显而易见的策略是按顺序构建排列,例如,在树中。然后每次切割消除整个分支。
编辑: 示例:在集合(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)。
嗯。对不起,我进入了演讲模式; 忍受我。
https://stackoverflow.com/questions/-100000845
复制相似问题