Cycledetection algorithm?
Author 
Message 
Christopher Jer #1 / 15

Cycledetection algorithm?
I'm working through SICP in my spare time to learn some things about programming, and came across the following exercise: 3.19 Write a procedure that determines, _in_constant_space_, whether a given list structure contains a cycle. This is easy to do in nonconstant space (just keep track of all the pairs along your path, and see whether you run into one you've seen before)  in fact, this is exercise 3.18. I came up with an idea that runs in _almost_ constant space, namely encoding the chain of `car' and `cdr' followed by a path into a large integer (2^n for a `cdr' in the nth place)  but this doesn't seem to be "real" constant space to me. Maybe this is more an algorithms question than a Scheme question (it's not a homework question!) so could anyone point me to a reference for an algorithm which does the trick in constant space? I'm a math student only recently interested in CS, and I don't know much about algorithms  the one reference I checked (Sedgewick's "Algorithms in Modula3") wasn't any help. Thank you... Christopher Jeris University of Chicago Math:

Fri, 07 Aug 1998 03:00:00 GMT 


Antoun Kanawa #2 / 15

Cycledetection algorithm?
: I'm working through SICP in my spare time to learn some things about : programming, and came across the following exercise: : : 3.19 Write a procedure that determines, _in_constant_space_, whether a : given list structure contains a cycle. Check Knuth's volumes for "pointer reversal", most probably in volume 3. My memory fades beyond this bit of trivia, but I think this is the kind of approach you need to look into.  Antoun (Tony) Kanawati
http://www.{*filter*}com.net/~tonyk/

Fri, 07 Aug 1998 03:00:00 GMT 


Bryan O'Sulliv #3 / 15

Cycledetection algorithm?
t> Check Knuth's volumes for "pointer reversal", most probably in t> volume 3. This is not a constantspace solution; it relies on using the stack to maintain old pointers. At least, it does if you want to put your structure back together again once you're done (and if you don't, then you're cheating). The constantspace solution makes use of the tortoiseandhare algorithm, and can easily be derived from the name of the algorithm alone. <b  Let us pray:

Fri, 07 Aug 1998 03:00:00 GMT 


Eugene Byo #4 / 15

Cycledetection algorithm?
Quote:
>3.19 Write a procedure that determines, _in_constant_space_, whether a >given list structure contains a cycle.
here's a hint: all you need are two pointers that initially point to the first cons cell of the list. using a loop, advance each pointer to visit successive elements of the list, but advance each pointer at a different "speed". hope this helps.  Eugene

Fri, 07 Aug 1998 03:00:00 GMT 


Joachim Flodqvis #5 / 15

Cycledetection algorithm?
Well, well.. Start by using two pointers; ptr1 & ptr2. Implement the following algorithm: *Send ptr1 forward one step *Check for equality. *Send both ptr1 and ptr2 forward one step. *Check for equality. Loop Incidentally this was a question on an exam a couple of years ago. (I'm also a student at RIT, the Royal Institute of Technology in Stockholm, Sweden) I implemented a more complicated version of the above scheme that used an array (fixed size) of pointers, each with a stepsize. I didn't get any points because the guy who corrected my exam didn't understand what I was trying to do. Ah, well... that's life. Btw. I'm curious if an algorithm using an array of different stepsize pointers would (on average) find the cycle faster than the twopointer method. That was the purpose of my algorithm, but I never got around to try and prove it. (never liked Ordo that much :)) /Joachim  Reporter <to Mahatma Gandhi>: Mr. Gandhi, what do you think of Western civilization ? Gandhi: I think it would be a good idea.

Fri, 07 Aug 1998 03:00:00 GMT 


Christopher Jer #6 / 15

Cycledetection algorithm?
Thanks to all who responded, for putting up with my silly elementary questions. The consensus answer was to use two pointers, one moving faster than the other, and see when they collide. This works easily for lists which are known to be linear or cyclic. For general list structures the answer is not quite so clear, but I think "two pointers" was the idea I needed. Thank you! Christopher Jeris University of Chicago Math:

Fri, 07 Aug 1998 03:00:00 GMT 


Henry Bak #7 / 15

Cycledetection algorithm?
Quote:
> Thanks to all who responded, for putting up with my silly elementary > questions. The consensus answer was to use two pointers, one moving faster > than the other, and see when they collide. This works easily for lists > which are known to be linear or cyclic. For general list structures the > answer is not quite so clear, but I think "two pointers" was the idea I > needed. Thank you!
The point isn't so much that one is 'moving faster than the other', but that the gcd of the two speeds is 1.  www/ftp directory: ftp://ftp.netcom.com/pub/hb/hbaker/home.html

Sat, 08 Aug 1998 03:00:00 GMT 


Richard A. O'Kee #8 / 15

Cycledetection algorithm?
Quote:
>I'm working through SICP in my spare time to learn some things about >programming, and came across the following exercise: >3.19 Write a procedure that determines, _in_constant_space_, whether a >given list structure contains a cycle.
The classic algorithm is "tortoise and hare". ;; UNTESTED CODE (let tortoiseandhare ((Tortoise X) (Hare X)) (and (not (null? Hare)) (not (null? (cdr Hare))) (or (eq? (cdr Hare) Tortoise) (eq? (cddr Hare) Tortoise) (tortoiseandhare (cdr Tortoise) (cddr Hare)) )) ) A well known technique for finding periods in constant space.  Election time; but how to get Labour _out_ without letting Liberal _in_? Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.

Sat, 08 Aug 1998 03:00:00 GMT 


MAEDA Atu #9 / 15

Cycledetection algorithm?
cdjeris> I'm working through SICP in my spare time to learn some things about cdjeris> programming, and came across the following exercise: cdjeris> 3.19 Write a procedure that determines, _in_constant_space_, whether a cdjeris> given list structure contains a cycle. [...deleted...] cdjeris> Maybe this is more an algorithms question than a Scheme question (it's cdjeris> not a homework question!) so could anyone point me to a reference for cdjeris> an algorithm which does the trick in constant space? I'm a math cdjeris> student only recently interested in CS, and I don't know much about cdjeris> algorithms  the one reference I checked (Sedgewick's "Algorithms in cdjeris> Modula3") wasn't any help. See the description of listlength function (section 15.2) in "Common Lisp the Language: 2nd edition" (Steele, et al., Digital Press; also available as http://www.cs.cmu.edu/Web/Groups/AI/html/cltl/cltl2.html or ftp://cambridge.apple.com/pub/CLTL/) mad

Sat, 08 Aug 1998 03:00:00 GMT 


Antoun Kanawat #10 / 15

Cycledetection algorithm?
Quote:
> This is not a constantspace solution; it relies on using the stack to > maintain old pointers. At least, it does if you want to put your > structure back together again once you're done (and if you don't, then > you're cheating).
You're probably right. As I've mentioned before, this tip came with a "faded memory" disclaimer. I remember some XOR trickery that "combined" values together, and avoided the stack. Of course, the disclaimer still stands :) 
http://www.{*filter*}com.net/~tonyk/

Sat, 08 Aug 1998 03:00:00 GMT 


Jake Donh #11 / 15

Cycledetection algorithm?
Christopher> 3.19 Write a procedure that determines, Christopher> _in_constant_space_, whether a given list structure Christopher> contains a cycle. One cute trick is the "tortoise and hare" method: Start two pointers at the head of the list. Now loop, advancing one pointer (the tortoise) by one pair, and the other (the hare) by two pairs. If the tortoise and the hare ever point to the same pair (except at the beginning of the algorithm) then you have a loop. If the hare gets to the end of the list then you have no loop. This algorithm takes O(N) time (once the tortoise has entered the loop, the hare is at most N jumps behind it, and each iteration brings the hare one jump closer to the tortoise). I think the pointerreversal method that someone mentioned goes like this: traverse the list; for each new pair you see, follow the cdrs for M steps (where M is the number of pairs you've seen so far) to see if you get back to the first pair in the list. If so, you've got a loop. If not, change the cdr of the current pair to point to the previous pair, and continue on to the next pair. If you reach the end of the list then you have no loop. It might help to draw a picture to see how this works. It takes O(N^2) time. Jake

Sun, 09 Aug 1998 03:00:00 GMT 


Ariel Scolnic #12 / 15

Cycledetection algorithm?
: I'm working through SICP in my spare time to learn some things about : programming, and came across the following exercise: : : 3.19 Write a procedure that determines, _in_constant_space_, whether a : given list structure contains a cycle. Check Knuth's volumes for "pointer reversal", most probably in volume 3. My memory fades beyond this bit of trivia, but I think this is the kind of approach you need to look into.  Antoun (Tony) Kanawati
http://www.{*filter*}com.net/~tonyk/ Not really  there's a great algorithm for finding loops. Traverse the list TWICE, with 2 separate pointers. One pointer goes twice as fast as the other, so every time p becomes (cdr p), q becomes (cdr (cdr q)). Now check p and q for equality, and q for the end of the list. Obviously, it's constant space (assuming you do it right). If there's a loop, q will "lap" p, and you'll get (eq? p g). If there is no loop, q will reach the end of the list.

Sun, 09 Aug 1998 03:00:00 GMT 


Richard Barnet #13 / 15

Cycledetection algorithm?
: > : > This is not a constantspace solution; it relies on using the stack to : > maintain old pointers. At least, it does if you want to put your : > structure back together again once you're done (and if you don't, then : > you're cheating). : You're probably right. As I've mentioned before, this tip came : with a "faded memory" disclaimer. I remember some XOR trickery : that "combined" values together, and avoided the stack. Of course, : the disclaimer still stands :) Well, I didn't see Tony's original post, but I do believe he's right about XOR trickery. There is a technique for encoding a doubly linked list with only a single pointer using XOR. Any algorithm proceeding along the lines of "walk the list saving previous pointers" could save the pointers by (temporarily) doubly linking the list using the XOR trick. Of course, this would play havoc with a shared structure in a multithreaded application. The technique relies on the following property of XOR: a XOR b XOR a = b If "next" and "prev" are the next and previous links in the doubly linked list, you store both of them as the single value next XOR prev If you have a pointer to one node in the list, and a pointer to either the next or previous node, you can recover the other pointer with an XOR.  Richard Barnette  This space  White's Chappaquidick Theorem: Data General/RTP  intentionally 
(919) 2486225   announce the bad news, the better.

Tue, 11 Aug 1998 03:00:00 GMT 


Tony Kanawa #14 / 15

Cycledetection algorithm?
Quote: (Barry Margolin) writes:
> >Well, I didn't see Tony's original post, but I do believe he's right > >about XOR trickery. There is a technique for encoding a doubly > >linked list with only a single pointer using XOR. > Of course, this doesn't work in Lispfamily languages. It only works in > lowlevel languages that represent pointers using integers. In Scheme > there are no explicit pointers, just object references, so there's no way > to XOR them. And even if you could get at the pointers, you'd have to > ensure that no GC occurs while your function is running.
XORing pointers in LISP is definitely gauche. But, I believe it is possible to do something with conscells such that f(f(a,b),a) => b, and f(f(a,b),b) = a. Given that the technique will ultimately involve some '!' suffixed procedure names and will do {*filter*} to the data structures under examination, it will run into problems dealing with immutable objects (supposedly things like '(x y z) are "constants"). 
 "There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies."  C.A.R. Hoare   Antoun (Tony) Kanawati, Senior Consultant, ONTOS Inc. 900 Chelmsford st., Lowell, MA 01851, USA 5083238000

Fri, 14 Aug 1998 03:00:00 GMT 


Barry Margol #15 / 15

Cycledetection algorithm?
Quote:
>Well, I didn't see Tony's original post, but I do believe he's right >about XOR trickery. There is a technique for encoding a doubly >linked list with only a single pointer using XOR.
Of course, this doesn't work in Lispfamily languages. It only works in lowlevel languages that represent pointers using integers. In Scheme there are no explicit pointers, just object references, so there's no way to XOR them. And even if you could get at the pointers, you'd have to ensure that no GC occurs while your function is running.  Barry Margolin BBN PlaNET Corporation, Cambridge, MA
Phone (617) 8733126  Fax (617) 8736351

Fri, 14 Aug 1998 03:00:00 GMT 


