有效地寻找独特的排列

Question

我有以下问题.我需要计算一组的排列; 但是,该集合可能包含两个相同的元素,因此会导致重复的排列.例如:

给定集合[ 0 0 1 2 ],排列包括这些可能性:

 1     2     0     0
 1     2     0     0

但是,我想避免像这些相同的排列.在MATLAB中,我可以简单地这样做:

unique(perms([ 0 0 1 2 ]), 'rows')

但这里的问题是效率 - 我在一个巨大的for循环中反复这样做,并且所需的排序unique太慢了.所以我的问题是:我可以直接计算这种性质的独特排列,而不必在事后循环结果吗？我在MATLAB工作,但只是一个通用的解决方案可能会有所帮助,虽然可以在MATLAB中矢量化的东西可能是理想的!

据我所知,现有的问题并不能完全解决这个问题,但如果以前已经回答了这个问题,我会道歉.

Answer 1

看来这是一个经常出现的问题。这是 John d'Errico ( ) 的一个文件uniqueperms，似乎可以非常有效地解决这个问题。作为替代方案，这里还有Ged Ridgway 提交的另一份 FEX 文章；您必须进行一些分析才能看出哪个更快。

请注意，由于 Matlab JIT 的限制，如果循环调用非内置函数，则循环不会加速，因此将这些函数的内容（和/或对其进行专门化）复制粘贴到循环中可能会有所帮助。 ）。