Попытка удалить дубликаты атомов, указанных в первом списке, из второго списка - PullRequest
Новая
       24

Попытка удалить дубликаты атомов, указанных в первом списке, из второго списка

1 голос
/ 04 октября 2011

Я пытаюсь написать функцию, которая работает как remove-duplicates, но вместо этого она принимает два списка в качестве входных данных: первый указывает символы, для которых дублирование не разрешено, а второй - список различных атомов, который долженбыть сокращенным.

В настоящее время у меня есть это: 

(defun like-remove-duplicates (lst1 lst2)
(if(member (first lst1) lst2)
    (remove-if #'(lambda (a b)
          (equals a b))lst1 lst2)))

Я знаю, что это не совсем близко, но я не могу понять, что мне нужно сделать для выполнения этой функции.Я знаю, что по сути нужно проверить, находится ли первый элемент в списке list1 в list2, и если это так, удалить его дубликаты (но оставить один), а затем перейти к следующему элементу в первом списке.Я предполагал рекурсию, но она не удалась.Я пытался исследовать, но безрезультатно.

Любая помощь?

Ответы [ 3 ]

3 голосов
/ 04 октября 2011 
CL-USER> (defun remove-duplicates-from-list (forbidden-list list)
           (reduce (lambda (x y)
                     (let ((start (position y x)))
                       (if start
                           (remove y x :start (1+ start))
                           x)))
                   forbidden-list
                   :initial-value list))
REMOVE-DUPLICATES-FROM-LIST

CL-USER> (remove-duplicates-from-list '(1 2) '(1 2 1 3))
(1 2 3)
CL-USER> (remove-duplicates-from-list '(1 2) '(1 2 1 3 2))
(1 2 3)
CL-USER> (remove-duplicates-from-list '(1 2) '(1 2 1 3 2 4))
(1 2 3 4)
CL-USER> (remove-duplicates-from-list '(2 1) '(1 2 1 3 2 4))
(1 2 3 4)
CL-USER> (remove-duplicates-from-list '(2 1) '(0 1 2 1 3 2 4))
(0 1 2 3 4)
CL-USER> (remove-duplicates-from-list '(2 1) '(0 2 3 2 4))
(0 2 3 4)
CL-USER> (remove-duplicates-from-list '(2 1) '(0 2 2 3 4))
(0 2 3 4)

Рекурсия выполняется reduce (потому что здесь у нас самый распространенный шаблон рекурсии: передать результат предыдущей итерации в следующую), а remove ing выполняется с помощью параметра :start, то есть смещение после первого столкновения (найдено position) значения, удаляемого в данный момент.

Также важно учитывать случай, когда значение не найдено и position возвращает nil.

2 голосов
/ 05 октября 2011

Нечто подобное должно работать и иметь приемлемую сложность по времени (за счет сложности пространства соема). 

(defun like-remove-duplicates (only-once list)
  "Remove all bar the first occurence of the elements in only-once from list."
  (let ((only-once-table (make-hash-table))
        (seen (make-hash-table)))
    (loop for element in only-once
     do (setf (gethash element only-once-table) t))
    (loop for element in list
     append (if (gethash element only-once-table)
                (unless (gethash element seen)
                  (setf (gethash element seen) t)
                  (list element))
              (list element)))))

При этом используются две таблицы состояний, обе из которых ограничены размером списка элементов для включения только один раз и должны быть приблизительно линейными в сумме длины двух списков.

0 голосов
/ 08 октября 2011 
(defun remove-listed-dups (a b)
  (reduce (lambda (x y) (if (and (find y a) (find y x)) x (cons y x)))
          b :initial-value ()))
...