开发者

Trying to remove duplicates of atoms specified in first list from second list

开发者 https://www.devze.com 2023-04-10 17:16 出处:网络
I\'m trying to write a function that works like remove-duplicates, but it instead takes two lists as input, the first specifying characters for which duplication is not allowed, and the second being a

I'm trying to write a function that works like remove-duplicates, but it instead takes two lists as input, the first specifying characters for which duplication is not allowed, and the second being a list of various atoms which is to be pruned.

Currently I have this:

(defun like-remove-duplicates (lst1 lst2)
(if(member (fir开发者_开发知识库st lst1) lst2)
    (remove-if #'(lambda (a b)
          (equals a b))lst1 lst2)))

I know it's not anywhere near right, but I can't figure out what I need to do to perform this function. I know I essentially need to check if the first item in list1 is in list2, and if so, remove its duplicates (but leave one) and then move onto the next item in the first list. I envisioned recursion, but it didn't turn out well. I've tried researching, but to no avail.

Any help?


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)

Recursion is performed by reduce (because here we have the most common recursion pattern: feed the result of previous iteration to the next) and removeing is done with the help of :start parameter, that is the offset after the first encounter (found by position) of the value being removed currently.

It's also important to account the case, when the value isn't found and position returns nil.


Something like this should work and have acceptable time-complexity (at the cost of soem space-complexity).

(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)))))

This uses two state tables, both bounded by the size of the list of elements to include only once and should be roughly linear in the sum of the length of the two lists.


(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 ()))
0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号