How to compute the number of cycles of a permutation in MATLAB?

Question

Given a permutation P = randperm(N) for $N\approx 10^6$.

How to compute the number of cycles of the permutation represented by P in MATLAB efficiently?

Answer 1

Brute force should do it pretty fast. Make a table with $N$ entries, all zeroes.

count = 0
repeat until more nonzero entries in table:
   pick the first nonzero entry $k0$ in the table
   table(k0) = 1
   count = count + 1
   k = k0

   repeat
      k = permutation applied to k
      table(k) = 1
   until k = k0

 print count

The "until no more nonzero entries" can be sped up by searching the table upwards starting from the current value of $k0$.

If you store your permutation in a sparse matrix or hashtable, you should be able to do this all in nearly O(N) time.