Common Lisp - 编写检测循环列表的函数

Question

我有一个 CS 函数式语言的作业 class，我们必须编写一个函数来检测给定列表的开头是否是循环的。该函数必须是递归的。我们将其命名为 circular :

* (setf list1 '(a b c d))
* (rplacd (cddr list1) list1)
* list1
#1=(A B C . #1#)
* (circular list1)
t
* (circular '(a b c a b c))
nil

现在，我知道在这种情况下如何检查循环性：在递归的某个时刻，列表中的 ~~atom~~a cons 将共享与列表本身相同的地址，因此循环。到目前为止，这是我的功能：

(defun circular (list &aux list2)
  (setf list2 list)
  (cond
    ((null list) nil)
    ((eq (car list) list2) t)
    (t (circular (cdr list))) ) )

我认为通过在递归的每个点比较 list 的 car 和 list2 函数最终会 return 结果，但是当函数确实适用于非循环列表，当我尝试在循环列表上使用它时，它会变得无限递归。我确信我在这里遗漏了一些非常明显的东西，但仍然非常感谢任何帮助！

Answer 1

您在每一步都丢掉了第二个值。您只是每次都将列表与其 car 进行比较，因此您只能捕获一种特殊的循环情况，即列表直接引用自身。

您需要做的是尝试所有的圆周长度。通常的方法是让两个引用以不同的速度在列表中移动。你只需要证明这将永远终止。

更新：是的，就是"turtle and hare"算法。您保留两个引用，您在每个循环中更新它们：一个前进一步，一步前进两步。这样，两个参考之间的距离每一步都会增加一个。一旦两个参考都进入圆（这可能会在列表的后面发生），只要该距离是圆长度的倍数，您就会使它们重合。

Answer 2

这个问题可以使用 tortoise and hare algorithm 来解决，其中有两个光标扫描 tortoise 一次一个缺点，并且 hare 从第二个元素开始以双倍速度扫描。如果乌龟和兔子是同一个元素，你就有一个循环。

(defun cyclicp (list)
  "check if a list is cyclic using tortoise and hare algorithm"
  (loop :for tortoise on list
        :for hare on (cdr list) :by #'cddr
        :thereis (eq tortoise hare)))

所以假设您有列表，#1=(a b c . #1#) 或更准确地说 '#1=(a . #2=(b . #3=(c . #1#)))。它包含 3 个 cons，地址为 1,2,3，每个 cons 都有一个符号值 a、b、c。

如果我写 car 的乌龟和兔子，你会看到兔子环绕并最终以与乌龟相同的 cons 结束

Iteration 1 2 3
Tortoise  a b c
Hare      b a c
              ^ match

您唯一需要做的就是使用递归重新实现它。它看起来像这样：

(defun cyclicp (list)
  "check if a list is cyclic using tortoise and hare algorithm"
  (labels ((aux (tortoise hare)
        (cond ((null hare) <??>)
              ((eq tortoise hare) <??>)
              (t (aux <??> <??>)))))
    (aux list (cdr list))))

编辑

一个简单且简单的版本，只检查对第一个 cons 的引用可以像这样完成：

(defun cyclic-1-p (list)
  "check if a list is cycles back to the first cons"
  (loop :for cursor on (cdr list)
        :thereis (eq cursor list)))

您唯一需要做的就是使用递归重新实现它。它看起来像这样：

(defun cyclic-1-p (list)
  "check if a list is cycles back to the first cons"
  (labels ((aux (cursor)
        (cond ((null cursor) <??>)
              ((eq cursor list) <??>)
              (t (aux <??>)))))
    (aux (cdr list))))

如果循环发生但不是在第一个 cons 这将不会终止。

(cyclic-1-p '(1 . #1=(2 3 . #1#))) ; never halts

Common Lisp - 编写检测循环列表的函数

Common Lisp - Writing a function that detects circular lists

lisp

recursion

function

list

common-lisp