Non-recursive implementation of perms in Matlab, compatible with Coder

Question

I am trying to convert part of my function in matlab into c++ using coder. Coder doesn't support the function perms. I extensively use perms in my code. After looking online I found few suggestions of how to generate a list of all permutations without perms but it is done "by hand", meaning that for permutations with 3 elements we have three for loops, with 4 elements we have 4 loops, etc.

Example for 1:4:

row = 1; 
n=a;
Z = zeros(factorial(n),n);
idxarray1=[1:4];

for idx=idxarray1
    idxarray2=idxarray1(find(idxarray1~=idx)) ;  
    for jdx=idxarray2
        idxarray3=idxarray2(find(idxarray2~=jdx)); 
        for kdx=idxarray3
            idxarray4=idxarray3(find(idxarray3~=kdx)) ;
            for mdx=idxarray4
                Z(row,:) = [idx,jdx,kdx,mdx];
                row = row + 1 ;
            end
        end
    end
end

For 8 elements I would have to write 8 for loops, any suggestions of how I can transform this for n elements? Something like

for i=n:-1:1
    I=[1:n] ;
    for j=1:i
       J=I(find(I~=j));

... ?


thank you

Answer 1

The problem here is that perms uses recursion, which is one of the language features that Matlab Coder does not support. So what we need to do is to come up with an implementation that is non-recursive.

Interestingly enough, perms was recursive before Matlab 6.0, then non-recursive, and then recursive again. So rather than inventing the wheel, we can just take one of the previous non-recursive revisions, e.g. 1.10.

Note that the order of the permutations is different, but you should not be relying on that in your code anyway. You might need to change the name to avoid the conflict with native perms function. Tested with coder.screener, which confirms that Coder supports it.

function P = perms(V)
%PERMS All possible permutations.
% PERMS(1:N), or PERMS(V) where V is a vector of length N, creates a
% matrix with N! rows and N columns containing all possible
% permutations of the N elements.
%
% This function is only practical for situations where N is less
% than about 10 (for N=11, the output takes over 3 giga-bytes).
%
% See also NCHOOSEK, RANDPERM, PERMUTE.

% ZP. You, 1-18-99 
% Copyright 1984-2000 The MathWorks, Inc.
% $Revision: 1.10 $ $Date: 2000/06/16 17:00:47 $

V = V(:)';
n = length(V);
if n == 0
   P = [];
else
   c = cumprod(1:n);
   cn = c(n);
   P = V(ones(cn,1),:);

   for i = 1:n-1; % for column 1 to n-1, switch oldidx entry with newidx entry
      % compute oldidx
      j = n-i;
      k = (n-j-1)*cn;
      oldidx = (c(j)+1+k:c(j+1)+k)';

      % spread oldidx and newidx over corresponding rows
      for k = j+1:n-1
         q = 0:c(k):k*c(k);
         shift = q(ones(length(oldidx),1),:);
         oldidx = oldidx(:,ones(1,k+1));
         oldidx = oldidx(:)+shift(:); 
      end

      % compute newidx
      colidx = cn:cn:j*cn;
      colidx = colidx(ones(c(j),1),:);
      colidx = colidx(:);
      colidx = colidx(:,ones(1,length(oldidx)/(j*c(j))));
      newidx = oldidx + colidx(:); 

      % do the swap
      q = P(newidx);
      P(newidx)=P(oldidx);
      P(oldidx)=q;
   end
end