循環リストの判定

Scheme 30分プログラム

30分プログラム、その606。循環リストの判定をしてみよう。

たしか昔、Common Lispの勉強をしてたときに判定アルゴリズムを読んだ気がする。
おっと、これだこれ。

循環リストのチェックは「うさぎとかめ」のアルゴリズムを使うと簡単です。「うさぎ」と「かめ」はリストをたどる変数として定義します。うさぎは cdr を 2 回適用して進みますが、かめは cdr を 1 回適用して進みます。うさぎがリストの終端に到達すれば、リストは循環していないことがわかります。うさぎがかめに追いつけば、リストは循環していると判断できます。プログラムは次のようになります。

ホームページ移転のお知らせ - Yahoo!ジオシティーズ

使い方

gosh> (define xs
  (let1 a '(1)
	(set-cdr! a a)
	a))
gosh> xs
#0=(1 . #0#)
gosh> (circular? xs)
#t
gosh> (circular? '(1 2 3))
#f

ソースコード

#! /opt/local/bin/gosh
;; -*- mode:scheme; coding:utf-8 -*-
;;
;; circular.scm -
;;
;; Copyright(C) 2009 by mzp
;; Author: MIZUNO Hiroki / mzpppp at gmail dot com
;; http://howdyworld.org
;;
;; Timestamp: 2009/06/19 21:00:07
;;
;; This program is free software; you can redistribute it and/or
;; modify it under MIT Lincence.
;;

(define (circular? xs)
  (define (iter xs ys)
    (cond
     [(or (null? xs) (null? ys)) #f]
     [(eq? (car xs) (car ys))    #t]
     [else (iter (cdr xs) (cddr ys))]))
  (iter xs (cdr xs)))

(define xs
  (let1 a '(1)
	(set-cdr! a a)
	a))
(circular? xs)
(circular? '(1 2 3))

参考