列表中所有匹配元素的位置

Question

我正在尝试在 Common Lisp 中编写一个类似于内置位置函数的函数，该函数返回大海捞针中与针匹配的所有元素的位置列表，而不是仅返回第一个。我提出了一些可能的解决方案（例如，在该位置上使用 cdr-from 函数递归搜索下一个元素并将结果添加到前一个位置），但到目前为止我还没有提出任何方法显得特别优雅。

任何人都可以建议什么是解决这个问题的最佳方法，因为我目前正在挣扎。

Answer 1

解决该问题的明显方法是依次查看列表中的每个元素，每次比较等于针时，将其位置收集到输出列表中。在这种情况下获取位置非常容易，因为我们从 haystack 的开头开始； 我们可以使用一个变量来从 0 开始计算当前位置。

因此，如果我们用句子中，我们会说类似“找到大海捞针在大海捞针中的所有位置，对于大海捞针中的每个元素，从0开始的位置，当该元素等于针时，收集该位置。”

当您想要进行迭代处理时，LOOP 工具基本上是正确的选择。尽管它的语法对于正式描述来说很复杂， 经过一些经验你几乎可以将算法的英文描述放在LOOP 的主体，它将起作用。

(defun all-positions (needle haystack)
  (loop
    for element in haystack 
    and position from 0
     when (eql element needle)
      collect position))

Answer 2

对此持保留态度（并确保事先加载Alexandria）：

(defun positions (item sequence &key (test #'eql))
  (mapcar #'car
          (remove item (map 'list #'cons (alexandria:iota (length sequence)) sequence)
                       :test-not test
                       :key #'cdr)))

也就是说，它确实具有处理任意序列的优点：

CL-USER> (positions 'x #(x x y y x x y y))
(0 1 4 5)
CL-USER> (positions 5 (list 5.0 -1 5 5.0 -1) :test #'=)
(0 2 3)
CL-USER> (positions #\l "Hello")
(2 3)

Answer 3

如果您想要一个递归函数，而不是基于 (loop ...) 的函数，您可以使用类似以下内容的函数：

(defun all-positions (needle haystack)
    (labels ((f (n h c r)
                 (if (null h)
                     r
                     (if (eql (car h) n)
                         (f n (cdr h) (1+ c) (cons c r))
                         (f n (cdr h) (1+ c) r))))))
    (reverse (f needle haystack 0 nil)))

Answer 4

这是另一种（不一定更好）的方法。

(defun get-positions (needle haystack)
  (let ((result nil))
    (dotimes (i (length haystack))
      (if (eq (nth i haystack) needle)
          (push i result)))
    (nreverse result)))