list - 如何检查列表中的所有数字是否都在稳步增加？

Question

我有几个长度不一的列表，其中包含简单的正整数，例如 (2 4 1 3)，我想检查列表排序后是否所有数字都在后面。这意味着顺序本身无关紧要，但不允许有间隙。

(2 4 1 3) 是正确的

(2 4 1 5) 不正确

在我开始重新发明轮子之前，我想知道是否有一种替代方法可以对列表进行排序，然后检查第一个和第二个(依此类推...)元素是否存在差异是 1。

编辑

我的例子没有显示完整的任务。该列表不必每次都以 1 开头，即 (6 8 7 9) 也可以是有效输入。

Answer 1

最优解

您需要检查列表定义的集合是否与[a:b]相同。这很容易通过创建 bit vector 来完成。适当的长度。这是列表长度的线性 (O(n))(需要扫描一次 length 和 min，一次填充位向量)，并且需要一些额外的向量临时内存:

(defun range-p (list)
  "Check that the list is identical to a..b as a set."
  (multiple-value-bind (min len)
      (loop for obj in list for len upfrom 0
        unless (integerp obj) do (return-from range-p nil)
        minimize obj into min
        finally (return (values min len)))
    (loop
      ;; 0: not seen this index in list yet
      ;; 1: already seen this index in list
      with indicator = (make-array len :element-type 'bit :initial-element 0)
      for obj in list for pos = (- obj min) do
        (unless (< pos len)
          ;; obj out of range
          (return-from range-p nil))
        (if (zerop (aref indicator pos))
            ;; obj is being seen for the 1st time; record that
            (setf (aref indicator pos) 1)
            ;; duplicate obj
            (return-from range-p nil)))
    ;; all list elements are unique and in the right range;
    ;; injectivity + same cardinality for finite sets => surjectivity
    t))

测试:

(range-p '(2 4 1 3))
==> T
(range-p '(2 4 1 5))
==> NIL
(range-p '(-1 5 3 4 2 1 0))
==> T
(range-p '(-1 5 3 4 3 1 0))
==> NIL
(range-p '(2 4 1 a 5))
==> NIL

排序

排序是线性的 (O(n*log(n)))，因此显然不是最优的。

附言

这可能与 Check consecutive numbers recursively using Lisp 有关.