Нерекурсивная реализация perms в Matlab, совместимая с Coder

Question

Я пытаюсь преобразовать часть моей функции в matlab в C++ с помощью кодера. Кодер не поддерживает функцию perms. Я широко использую perms в своем коде. После поиска в Интернете я нашел несколько предложений о том, как сгенерировать список всех перестановок без perms, но это делается «вручную», что означает, что для перестановок с 3 элементами у нас есть три для циклов, с 4 элементами у нас есть 4 цикла и т. Д.

Пример 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 

для 8 элементов я бы писать 8 для петель, любые предложения о том, как я могу преобразовать это для п элементов? Что-то вроде

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

... ? 


thank you 

Answer 1

Проблема здесь в том, что perms использует рекурсию, которая является одной из особенностей языка, которые Matlab Coder не поддерживает. Итак, что нам нужно сделать, это создать нерекурсивную реализацию.

Интересно, что perms был рекурсивным до Matlab 6.0, затем нерекурсивным, а затем рекурсивным снова. Поэтому вместо того, чтобы изобретать колесо, мы можем просто взять одну из предыдущих нерекурсивных ревизий, например. 1.10.

Обратите внимание, что порядок перестановок отличается, но в любом случае вы не должны полагаться на это в своем коде. Возможно, вам придется изменить имя, чтобы избежать конфликта с функцией perms. Протестировано с coder.screener, что подтверждает, что Coder поддерживает его.

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