Hi Richard, Am 09.12.2013 04:00, schrieb Richard A. O'Keefe:
[...] Here's a piece of computer science that I would like some help with. I call it the Indirect Cycle Detection problem.
Given: Domains P and E, functions f : P -> Maybe P g : P -> E
Define to_list :: Maybe P -> [E] to_list Nothing = [] to_list (Just p) = g p : to_list (f p)
Given: That f is cyclic starting at p0.
Find: The shortest alpha, beta such that to_list p0 is alpha ++ cycle beta and do so *efficiently*.
Now, I can use tortoise-and-hare to find a cycle in f and then use brute force to find a shortest prefix and cycle of to_list ... The stuff I've checked so far about periods in strings has nothing to say about periods that begin _after_ a non-empty prefix.
I am not sure if you're really looking for help here or just wanted to present an example. I assume the former. Also, I can not see where this "non-empty prefix" notion comes from. Perhaps you have a different definition for cyclic? For me: "f is cyclic starting at p0" means there exist an N>0 such that f^N p0 == p0. Let's assume n to be the smallest number that fulfills this condition and call it the period length of f_p0. f_p0 defines a periodic list ps with the same period length n. ps = map fromJust $ iterate (>>= f) (Just p0) Your (to_list p0), which I'd like to call es could now be written as: es = map g ps We know that es has a period of length n, but if g is not injective, its smallest period of length k may be smaller than n. period_n = take n es To find k, we search for the second occurrence of period_n in (period_n ++ period_n), knowing that it will be at position n, if it is not found at positions [1..n-1]. We might use the fact that it can only be in positions that divide n. On the other hand, we could just use any of the well known string-search-methods. Efficiency: - If computation of f is done in constant time, finding n takes Theta(n) time. Just apply f until you reach p0 again. - Searching a pattern of size n in a text of size 2n can be done in O(n) using the Knuth-Morris-Pratt-algorithm. In total you have a linear algorithm for finding your result: alpha = [] beta = take k es = take k period_n ***** Of course, I guess now you're going to tell me that your "non-empty prefix" means that the period of f is not starting at p0 but at some pi that is reached by applying f i times to p0. You can adapt to that, but you have to pay for it ;-) In this case, ps has the form (prefix ++ (cycle p_period_n)) and to find this structure, you need to find the first element of ps that occurs twice. (Before, you knew this would be p0.) For that, you need a set implementation for elements of P that gives you efficient adding of one element and lookup. Since we know nothing about P's elements, we use the list itself and get a runtime of Theta((i+n)^2). Finding the (smallest) period k in es is exactly the same as before, i.e. we look for the second occurrence of period_n in (period_n ++ period_n) with period_n = map g p_period_n The prefix does not bother us here, because we know that we are looking at the periodic part. Now that we know the period length k, we still have to find where it starts. For that we start at position i and go backwards until we find a difference to the found out period. That is, we find the position of the first mismatch between (reverse $ take i es) and (cycle (reverse $ take k period_n)). The index tells us the length of alpha and the rotation needed to get beta from (take k period_n). The cost for that is O(i). So, the total cost in this case would be O((i+n)^2 + n + i). I could have implemented this in Haskell, but since the point in the original discussion was about not needing programmer skills, but CS skills, I refrained from it. Haskell is only used to clarify points, in a language which both he recipient and the recipient know. :-) Thomas