function to remove duplicate elements from list ?

Discussion in 'Cadence' started by SS, Dec 28, 2005.

  1. SS

    SS Guest

    Is there a function to remove duplicate elements from a list

    thanks,
    Sriram
     
    SS, Dec 28, 2005
    #1
  2. SS

    Jimka Guest

    Do you want to convert (1 2 3 4 1 2 3 4 5) to (1 2 3 4 5)
    or do you want to remove all elements that
    are duplicates leaving only (5)? Also do you care
    about the order of the returned list?

    Here are a few helper function... untested.


    ;; ( 1 2 3 4 2 3 ) --> ( 2 3)
    ;; order N^2/2
    (defun find_duplicates (thelist)
    (setof x thelist
    (member x (cdr (member x thelist)))))

    ;; ( 1 2 3 4 2 3) --> ( 1 4)
    ;; order N^2/2
    (defun remove_duplicates (thelist)
    (setof x thelist
    (not (member x (cdr (member x thelist))))))

    ;; (1 2 3 4 2 3 ) --> ( 2 3 1 4)
    ;; order N^2
    (defun uniqify (thelist)
    (nconc (find_duplicates thelist)
    (remove_duplicates thelist)))

    another way to uniqify a list is by using a hash table

    (defun uniqify (thelist)
    (let ((hash (makeTable 'uniq nil)))
    (foreach x thelist
    hash[x] = t)
    hash->?))
     
    Jimka, Dec 29, 2005
    #2
  3. SS

    Jimka Guest

    oops my find_duplicates does not do so well if elements are repeated
    multiple times.
    find_duplicates called on '( 1 2 3 2 4 3 5 4 6 5 3 1 )
    returns (1 2 3 2 4 3 5 4 5 3 1),
    which is not good :-(

    A hash table aproach would be easier i think...

    ;; this function returns a hash table that maps
    ;; each element of a given list to the number of times
    ;; it occurs in the list.
    (defun uniq_hash (thelist)
    (let ((hash (makeTable 'dups 0)))
    (foreach x thelist
    hash[x] = 1 + hash[x])
    hash))

    ;; ( 1 2 3 2 4 3 5 4 6 5 3 1 )
    ;; --> (5 4 3 2 1)
    (defun find_duplicates (thelist)
    (let ((hash (uniq_hash thelist)))
    (setof x hash->?
    1 < hash[x])))

    ;; ( 1 2 3 2 4 3 5 4 6 5 3 1 )
    ;; --> (6 5 4 3 2 1)
    (defun uniqify (thelist)
    (uniq_hash thelist)->?)

    ;; ( 1 2 3 2 4 3 5 4 6 5 3 1 )
    ;; --> (6)
    (defun remove_duplicates (thelist)
    (let ((hash (uniq_hash thelist)))
    (setof x hash->?
    (onep hash[x]))))
     
    Jimka, Dec 29, 2005
    #3
  4. Here is mine, using tconc


    procedure(XXXuniqify(theList)
    let((newList)
    foreach(element theList
    unless(member(element car(newList))
    newList = tconc(newList element)
    );unless
    );foreach
    car(newList)
    );let
    );procedure


    XXXuniqify(list(1 2 3 1 2 5))
    => (1 2 3 5)

    Note that the order is preserved.

    regards,
    Suresh
     
    Suresh Jeevanandam, Dec 29, 2005
    #4
  5. SS

    Jimka Guest

    Here is the most efficient one i can think of.
    it preserves order (from right to left, whereas suresh's
    preserves order from left to right).

    (defun uniquify (thelist)
    (let ((list2 thelist))
    (foreach mapcan element thelist
    (pop list2)
    (unless (member element list2)
    (list element)))))

    Unfortunatly, SKILL does not have a mapping function which both
    iterates as map and maplist do but returns nconc'ed lists like
    mapcan does. If such a mapping function existed, you could write
    uniquify without
    the list2 tmp variable and without the call to pop. E.g., suppose
    there
    were a MAPN function, sort of a mixture between map and mapcan

    (defun uniquify (thelist)
    (foreach MAPN elements thelist
    (unless (member (car elements) (cdr elements))
    (list (car elements)))))
     
    Jimka, Dec 30, 2005
    #5
  6. SS

    SS Guest

    Thanks Suresh, Jimka

    Sriram
     
    SS, Dec 30, 2005
    #6
Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.