Cycle-detection algorithm?
Author Message
Cycle-detection 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
Modula-3") wasn't any help.

Thank you...

Christopher Jeris               University of Chicago Math:

Fri, 07 Aug 1998 03:00:00 GMT
Cycle-detection 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
Cycle-detection algorithm?

t> Check Knuth's volumes for "pointer reversal", most probably in
t> volume 3.

This is not a constant-space 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 constant-space solution makes use of the tortoise-and-hare
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
Cycle-detection 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
Cycle-detection 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 step-size. 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 step-size pointers would
(on average) find the cycle faster than the
two-pointer 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
Cycle-detection 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
Cycle-detection 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
Cycle-detection 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 tortoise-and-hare ((Tortoise X) (Hare X))
(and (not (null? Hare))
(not (null? (cdr Hare)))
(or (eq? (cdr  Hare) Tortoise)
(eq? (cddr Hare) Tortoise)
(tortoise-and-hare (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
Cycle-detection 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> Modula-3") wasn't any help.

See the description of list-length 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/)

Sat, 08 Aug 1998 03:00:00 GMT
Cycle-detection algorithm?

Quote:

> This is not a constant-space 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
Cycle-detection 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 pointer-reversal 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
Cycle-detection 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
Cycle-detection algorithm?
: >
: > This is not a constant-space 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 multi-threaded 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) 248-6225          |               | announce the bad news, the better.

Tue, 11 Aug 1998 03:00:00 GMT
Cycle-detection 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 Lisp-family languages.  It only works in
> low-level 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 cons-cells 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  508-323-8000

Fri, 14 Aug 1998 03:00:00 GMT
Cycle-detection 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 Lisp-family languages.  It only works in
low-level 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) 873-3126 - Fax (617) 873-6351

Fri, 14 Aug 1998 03:00:00 GMT

 Page 1 of 2 [ 15 post ]

Relevant Pages