有效地找到独特的排列 [英] Finding unique permutations efficiently

问题描述

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

I have the following problem. I need to compute the permutations of a set; however, the set may contain two elements which are the same and therefore cause repeated permutations. For example:

鉴于集合[ 0 0 1 2 ]，排列包括以下可能性:

Given the set [ 0 0 1 2 ], the permutations include these possibilities:

 1     2     0     0
 1     2     0     0

但是，我想避免类似的排列.在MATLAB中，我可以简单地做到这一点:

However, I would like to avoid identical permutations such as these. In MATLAB I can simply do this:

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

但是这里的问题是效率-我在一个很大的for循环中反复进行此操作，并且unique所需的排序速度太慢.所以我的问题是:我可以直接 直接计算这种性质的唯一排列而不必随后遍历结果吗?我在MATLAB中工作，但是一般的解决方案可能会有所帮助，尽管可以在MATLAB中向量化的东西可能是理想的选择！

But the problem here is efficiency - I am doing this repeatedly in a huge for loop and the sorting required by unique is too slow. So my question is: can I compute unique permutations of this nature directly without having to loop through the result afterwards? I am working in MATLAB but just a general solution would probably be helpful, although something which can be vectorized in MATLAB would probably be ideal!

据我所知，现有的问题并不能完全解决这个问题，但是如果以前已经回答过，我们深表歉意.

As far as I can see existing questions do not cover exactly this problem, but apologies if this has been answered before.

推荐答案

这似乎是一个经常发生的问题. 此处是John d'Errico(uniqueperms)编写的文件非常有效地解决它.另一种选择是，Ged Ridgway在此处 ;您将需要进行一些分析，以了解哪一个速度更快.

It would appear this is a regularly occurring problem. Here is a file by John d'Errico (uniqueperms) that seems to tackle it pretty effectively. As an alternative, there is another FEX submission here by Ged Ridgway; you'll have to profile a bit to see which one is faster.

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

Note that due to the limitations of Matlab's JIT, loops are not accelerated if they call non-builtin functions, so it might be beneficial to copy-paste the contents of these functions (and/or specialize them a bit) inside your loop(s).

这篇关于有效地找到独特的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！