Finding all cycles

Question

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.

Answer 1

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:

1. If A[s] = (fully explored), skip to step 6.
2. Set A[s] ← (partially explored), and set an iterator j ← f(s).
3. While A[j] = (unexplored), set A[j] ← (partially explored), and set j ← f(j).
4. 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.
5. 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).
6. 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.)

Answer 2

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 p^th powers for some integer p. For each s ∈ S, do the following:

1. If s is in samples, skip to step #5.
2. Initialize an empty list cursample, an iterator j ← f(s), and a counter t ← 1.
3. While j is not in samples:
   — If t ∈ G, insert j into both cursample and samples.
   — Increment t and set j ← f(j).
4. 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 complist.
5. 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) = n^1/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) = n^1/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 n² / 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(n² 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(n² 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(n² log X(n)) time to do so, where X(n) is the expected number of cycles.

Answer 3

You can avoid the multiple passes over the same elements by using a union set data-structure. One pass over each element $s$ unioning the set containing $s$ with the set containing $f(s)$. This still uses a lot of memory.