MATLAB: Permutations Cycles Counting … speed up

MATLABspeed upvectorization

Hi, this is my code for permutation cycles counting. Any idea how to vectorize it to get some additional speedup for large set of permutations?
function count = PermCyclesCount(p)
[nR,nE] = size(p);
count = zeros(nR,1);
for j = 1:nR
    i = 0;
    count(j) = 0;
    while i < nE
        i = i + 1;
        if p(j,i) > 0
            flag = false;  % flag is just to trick the computer into entering the while loop
            first = i;
            while (first ~= i) || ~flag
                flag = true;
                r = first;
                first = p(j,first);
                p(j,r) = 0;  % The entries in the cycle are changed to zero to indicate that they have been `used'
            end
            count(j) = count(j) + 1;
        end
    end
end
end
Some testing data:
[~,perms] = sort(rand(1000000,60),2);
tic;c= PermCyclesCount(perms);toc
Elapsed time is 1.559758 seconds.

Best Answer

% VERSION 1
[nR, nE] = size(p);
count    = zeros(nR, 1);
for j = 1:nR
   q = p(j, :);   % <== Cut out a vector to operate on
   i = 0;
   while i < nE
      i = i + 1;
      if q(i) > 0
         flag  = false;
         first = i;
         while (first ~= i) || ~flag
            flag  = true;
            r     = first;
            first = q(first);
            q(r)  = 0;
         end
         count(j) = count(j) + 1;
      end
   end
end
This tiny change let the code run in 1.41 instead of 2.37 sec on my computer.
And this in 1.25 sec without the flag:
% VERSION 2
[nR, nE] = size(p);
count    = zeros(nR, 1);
for j = 1:nR
   q = p(j, :);
   for i = 1:nE
      if q(i) > 0
         f    = q(i);
         q(i) = 0;
         while f ~= i
            r    = f;
            f    = q(f);
            q(r) = 0;
         end
         count(j) = count(j) + 1;
      end
   end
end
Related Question