Положение всех соответствующих элементов в списке

Question

Я пытаюсь написать в Common Lisp функцию, похожую на встроенную функцию position, которая возвращает список позиций всех элементов в стоге сена, которые соответствуют игле, в отличие от только первого.Я предложил несколько возможных решений (например, рекурсивный поиск следующего элемента с использованием функции 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

Возьмите это с зерном соли (и обязательно загрузите Александрия заранее):

(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

Вот еще один (не обязательно лучший) способ сделать это.

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

Answer 4

Если вам нужна рекурсивная функция, а не основанная на (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)))