function to remove duplicate elements from list ?

[SS]

Is there a function to remove duplicate elements from a list

thanks,
Sriram

 

[Jimka]

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]

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

 

[Suresh Jeevanandam]

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

 

[Jimka]

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

 

[SS]

Thanks Suresh, Jimka

Sriram