Finding unique permutations efficiently
combinatorics, math, matlab, permutation
Solution
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.
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).
Problem
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: Given the set `[ 0 0 1 2 ]`, the permutations include these possibilities: ``` 1 2 0 0 1 2 0 0 ``` 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') ``` 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.