Unique perms

From QETLAB
Jump to: navigation, search
unique_perms
Computes the unique permutations of a vector

Other toolboxes required none
Function category Helper functions
License license_unique_perms.txt
This is a helper function that only exists to aid other functions in QETLAB. If you are an end-user of QETLAB, you likely will never have a reason to use this function.

unique_perms is a function that computes all distinct permutations of a vector. Thus is produces the same output as using the built-in MATLAB commands unique(perms(V),'rows'), but it is significantly faster if there are many repetitions in the vector.

Syntax

  • PERM_LIST = unique_perms(V)

Argument descriptions

  • V: The vector to be permuted.

Examples

The following generates all unique permutations of the vector [1,1,2,2,1,2,1,3,3,3] in two different ways: using this unique_perms function, and by using matlab's built-in unique and perms functions. Using the unique_perms function is much faster when the vector has lots of repetitions (as in this case).

>> v = [1,1,2,2,1,2,1,3,3,3];
>> tic; length(unique_perms(v)) % fast method
   toc
 
ans =
 
        4200

Elapsed time is 0.300853 seconds.
 
>> tic; length(unique(perms(v),'rows')) % slow method
   toc
 
ans =
 
        4200

Elapsed time is 4.559448 seconds.

Source code

Click on "expand" to the right to view the MATLAB source code for this function.

  1. %%  UNIQUE_PERMS    Computes the unique permutations of a vector
  2. %   This function has one required argument:
  3. %     V: a vector
  4. %
  5. %   PERM_LIST = unique_perms(V) is list of unique permutations of a vector.
  6. %   
  7. %   This function does the same thing as unique(perms(v),'rows'), but is 
  8. %   much faster and less memory-intensive in most cases.
  9. %
  10. %   URL: http://www.qetlab.com/unique_perms
  11.  
  12. %   requires: nothing
  13. %   author: John D'Errico
  14. %	package: QETLAB 
  15. %	last updated: November 27, 2014
  16.  
  17. function perm_list = unique_perms( v )
  18.  
  19. uv = unique(v);
  20. n = length(v);
  21. nu = length(uv);
  22.  
  23. if nu <= 1
  24.     perm_list = v;
  25. elseif n == nu
  26.     perm_list = perms(v);
  27. else
  28.     perm_list = cell(nu,1);
  29.     for j = 1:nu
  30.         vt = v;
  31.         vt(find(vt==uv(j),1)) = [];
  32.         t = unique_perms(vt);
  33.         perm_list{j} = [repmat(uv(j),size(t,1),1),t];
  34.     end
  35.     perm_list = cell2mat(perm_list);
  36. end
  37.  
  38. end

External links