If you have very few cycles, here's an algorithm which will use less space, but take substantially longer to terminate.
[Edit.] My previous run-time analysis missed the crucial cost of determining whether the nodes we visit are among those previously sampled; this answer has been somewhat revised to correct this.
We again iterate through all of the elements of S. As we explore orbits of the elements s ∈ S, we sample from the nodes that we've visited, in order to be able to check if we come across them again. We also maintain a list of samples from of 'components' — unions of orbits which terminate in a common cycle (and which are therefore equinumerous to cycles) — that have previously been visited.
Initialize an empty list of components,
complist. Each component is represented by a collection of samples from that component; we also maintain a search tree
samples which stores all those elements which have been selected as samples for some component or other. Let G be a sequence of integers up to n, for which membership is efficiently determinable by computing some boolean predicate; for example, powers of 2 or perfect pth powers for some integer p.
For each s ∈ S, do the following:
- If s is in
samples, skip to step #5.
- Initialize an empty list
cursample, an iterator j ← f(s), and a counter t ← 1.
- While j is not in
— If t ∈ G, insert j into both
— Increment t and set j ← f(j).
- Check to see if j is in
cursample. If not, we have encountered a previously explored component: we check which component j belongs to, and insert all of the elements of
cursample into the appropriate element of
complist to augment it. Otherwise, we have re-encountered an element from the current orbit, meaning that we have traversed a cycle at least once without encountering any representatives of previously-discovered cycles: we insert
cursample, as a collection of samples from a newly found component, into
- Proceed to the next element s ∈ S.
For n = |S|, let X(n) be a monotone increasing function describing the expected number of cycles (e.g. X(n) = n1/3), and let Y(n) = y(n) log(n) ∈ Ω(X(n) log(n)) be a monotone increasing function determining a target for memory usage (e.g. y(n) = n1/2). We require y(n) ∈ Ω(X(n)) because it will take at least X(n) log(n) space to store one sample from each component.
The more elements of an orbit we sample, the more likely we are to quickly select a sample in the cycle at the end of an orbit, and thereby quickly detect that cycle. From an asymptotics point of view, it then makes sense to obtain as many samples as our memory bounds permit: we may as well set G to have an expected y(n) elements which are less than n.
— If the maximum length of an orbit in S is expected to be L, we may let G be the integer multiples of L / y(n).
— If there is no expected length, we may simply sample once every n / y(n) elements; this is in any case an upper bound on the intervals between samples.
If, in seeking a new component, we begin to traverse elements of S which we have previously visited (either from a new component being discovered or an old one whose terminal cycle has already been found), it will take at most n / y(n) iterations to encounter a previously sampled element; this is then an upper bound on the number of times, for each attempt to find a new component, we traverse redundant nodes. Because we make n such attempts, we will then redundantly visit elements of S at most n2 / y(n) times in total.
The work required to test for membership in
samples is O(y(n) log y(n)), which we repeat at every visitation: the cumulative cost of this checking is O(n2 log y(n)). There is also the cost of adding the samples to their respective collections, which cumulatively is O(y(n) log y(n)). Finally, each time we re-encounter a previously discovered component, we must expend up to X(n) log* y(n) time to determine which component we rediscovered; as this may happen up to n times, the cumulative work involved is bounded by n X(n) log y(n).
Thus, the cumulative work performed in checking whether the nodes we visit are among the samples dominate the run-time: this costs O(n2 log y(n)). Then we should make y(n) as small as possible, which is to say O(X(n)).
Thus, one may enumerate the number of cycles (which is the same as the number of components which end in those cycles) in O(X(n) log(n)) space, taking O(n2 log X(n)) time to do so, where X(n) is the expected number of cycles.