CODEWITHSUNDEEP
listrecursionlispcommon-lisp
Sean Glover
Sean Glover

Reputation: 520

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

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 (first 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?

Upvotes: 1

Views: 672

Answers (3)

huaiyuan
huaiyuan

Reputation: 26539

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

Upvotes: 0

Vatine
Vatine

Reputation: 21258

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.

Upvotes: 2

Vsevolod Dyomkin
Vsevolod Dyomkin

Reputation: 9451

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.

Upvotes: 3

Related Questions