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

Я пытаюсь преобразовать часть своей функции в Matlab в С++ с помощью кодера. Coder не поддерживает функцию perms. Я широко использую perms в своем коде. После поиска в Интернете я нашел несколько предложений о том, как создать список всех перестановок без perms, но это делается «вручную», что означает, что для перестановок с 3 элементами у нас есть три цикла for, с 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, какие-либо предложения о том, как я могу преобразовать это для n элементов? Что-то типа

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

... ?


thank you

c++ matlab permutation matlab-coder perms
person Mia    schedule 28.05.2016    source источник
comment
std::next_permutation   -  person 101010    schedule 29.05.2016
comment
@ 101010, это бесполезно, поскольку OP сам не переводит код на C ++. Для этого он полагается на Matlab Coder, а это значит, что ему приходится использовать только те функции Matlab, которые можно перевести.   -  person nirvana-msu    schedule 29.05.2016

Ответы (1)


arrow_upward
5
arrow_downward

Проблема здесь в том, что 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
person nirvana-msu    schedule 28.05.2016