I have a finite set $S$, a function $f:S\to S$, and a total order $<$ on $S$. I want to find the number of distinct cycles in $S$.For a given element $s\in S$ I can use Floyd's algorithm (or Brent's, etc.) to find the length of the cycle that repeated applications of $f$ sends $s$ to; with a bit more effort I can identify this cycle (e.g. by its $<$-minimal element).  A bad method for solving the problem would be to repeat this each element, sort the resulting minimal elements discarding duplicates, and return the count.  But this potentially involves many passes over the same elements and large space requirements.What methods have better time and space performance?  I'm not even sure what's the best way to measure the space needed—if $f$ is the identity function then any method that stores all cycles will use $\Omega(n)$ space.
Finding all cycles
graph theory;graph algorithms
If all that you want to do is count the number of cycles, you can do this with 2|S| bits (plus change) worth of space. It seems unlikely that you will be able to do much better unless S or f have some particularly convenient properties.Start with an array A storing integers {0,1,2} — one per element of S — initialized to zero; we will indicate these as (unexplored), (partially explored), and (fully explored). Initialize a cycle counter to zero. For each element s ∈ S in order, do the following:If A[s] = (fully explored), skip to step 6.Set A[s] ← (partially explored), and set an iterator j ← f(s).While A[j] = (unexplored), set A[j] ← (partially explored), and set j ← f(j).If A[j] = (partially explored), we have closed a new cycle; increment c by 1. (If you want to keep a record of some representative of this cycle, the current value of j will do as an arbitrary choice; of course, this won't necessarily be the minimal element in the cycle under your preferred order <.) Otherwise, we have A[j] = (fully explored), which means that we have discovered a pre-explored orbit which ends in an already counted cycle; do not increment c.To indicate that the orbit starting at s has now been fully explored, set j ← s. While A[j] = (partially explored), set A[j] ← (fully explored) and set j ← f(j).Proceed to the next element s ∈ S. Thus, each cycle among the orbits induced by f will be counted once; and any elements you record as representatives will be elements of distinct cycles. The memory requirements are 2|S| for the array A, O(log |S|) for the cycle count, and other odds and ends.Each element s ∈ S will be visited at least twice: once when the value of A[s] is changed from (unexplored) to (partially explored), and once for the change to (fully explored). The total number of times that any nodes are revisited after having been (fully explored) is bounded above by the number of attempts to find new cycles which fail to do so, which is at most |S| — arising from the main loop iterating through all elements of S. Thus, we can expect this process to involve at most 3|S| node-traversals, counting all the times that nodes are visited or revisited. If you want to keep track of representative elements of the cycles, and you really would like them to be the minimal elements, you can bound the number of node visitations to 4|S|, if you add an additional lap around the cycle at step 4 to find a representative which is smaller than the one where you close the loop. (If the orbits under f consisted only of cycles, this extra work could be avoided, but that's not true of arbitrary f.)