9
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ One of the natural ways to measure the space is to consider S as the set of n-bit strings and f as an oracle. Then the naive algorithm which you described requires exponential space. One may seek for an algorithm which uses only polynomial space, but this does not sound likely to be possible to me. $\endgroup$ – Tsuyoshi Ito Aug 23 '11 at 14:20
  • $\begingroup$ That's what I meant by "I don't know what's the best way to measure space". Possibly I should target O(poly(n) + y) where y is the output, so that space used is polynomial as long as y is sufficiently small. $\endgroup$ – Charles Aug 23 '11 at 14:57
  • $\begingroup$ Does your function f have any usable properties? Whether or not the algorithm is polynomial or exponential in your preferred way of expressing the input size will be somewhat moot if the practical answer is that the algorithm will take both time and space on the order of the cardinality of S. $\endgroup$ – Niel de Beaudrap Aug 23 '11 at 15:08
  • $\begingroup$ @Niel de Beaudrap: I'm not sure what properties would be useful. I expect that the number of distinct cycles is small, though, probably $O(\sqrt[3]n)$; that's why I suggested a function of $y$ and $n$ instead of just $n$. I'm willing to use space exponential in the number of bits of output, if needed. $\endgroup$ – Charles Aug 23 '11 at 15:29
7
$\begingroup$

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.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Excellent, this improves on the silly $O(|S|\log|S|)$ space algorithm I had in mind. I don't actually need representatives; I introduced $<$ just in case it would be useful to some algorithm. $\endgroup$ – Charles Aug 23 '11 at 17:59
  • $\begingroup$ I wonder if there's a way to use much less space in the case where there are few total cycles without using more than polynomial space. Ah, no matter; this will do for my needs. $\endgroup$ – Charles Aug 23 '11 at 18:05
  • 1
    $\begingroup$ It seems to me that this should be in #L (using matrix powering). Can this be #L-hard? $\endgroup$ – Kaveh Aug 23 '11 at 19:20
  • $\begingroup$ @Charles: see my more recent answer which will give you improvements if you know that #cycles ∈ o(|S|). It's uses more than polylog |S| space, but if you're willing to trade off space and time it may be better for you. $\endgroup$ – Niel de Beaudrap Aug 23 '11 at 20:11
  • $\begingroup$ @Niel de Beaudrap: Thank you! +1 for both. This algorithm seems best as long as the data fits in-memory; once it spills out I'll look at using the other. (It's possible that the other would be better if I could fit everything in cache, but that may be too much hassle.) $\endgroup$ – Charles Aug 23 '11 at 20:41
5
$\begingroup$

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:

  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)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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.