Finding unique elements of a list

Erik Reitsma EJ (RY/ETM) <>
Fri Dec 3 10:27:53 CET 2004


So what you are saying is, that it is a simple one-liner?

remove_dups(L) ->
 [F||{_,F}<-lists:sort(lists:foldl(fun({H,K},[{_,H}|_]=OL) -> OL; ({H,K},[{K1,H1}|T]) -> [{K,H},{K1,H1}|T]; ({H,K},[]) -> [{K,H}] end,[],lists:sort(element(1,lists:foldl(fun(E,{ResN,CountN}) -> {[{E,CountN}|ResN],CountN+1} end,{[],0},L)))))].

or, not on one line:

remove_dups(L) -> 
   [F||{_,F}<-
      lists:sort(
	   lists:foldl(
	      fun({H,K},[{_,H}|_]=OL) -> 
               OL;
            ({H,K},[{K1,H1}|T]) -> 
               [{K,H},{K1,H1}|T]; 
            ({H,K},[]) -> 
               [{K,H}] 
            end,
            [],
            lists:sort(
               element(
                  1,
                  lists:foldl(
                     fun(E,{ResN,CountN}) -> 
                        {[{E,CountN}|ResN],CountN+1}
                     end,
                     {[],0},
                     L)
               )
            )
         )
      )
   ].


:)

> If you want to remove duplicate elements from a list but otherwise
> preserve the order of the elements, so that, e.g., 
> 
>     remove_dups([3,1,4,1,5,9,2,6,5,3,5,8,9]) -> [3,1,4,5,9,2,6,8]
> 
> then there is an O(N.lgN) method which goes like this:
>     (1) pair each element with its position number in the list
> 	O(N)
>     (2) sort the list of pairs (using whole pairs as keys)
> 	O(N.lgN)
>     (3) remove adjacent duplicates
> 	O(N)
>     (4) switch the {Elem,Posn} pairs to {Posn,Elem} pairs
> 	O(U) where 1 <= U <= N, U is the number of unique elements
>     (5) sort the list of {Posn,Elem} pairs
> 	O(U.lgU)
>     (6) strip off the positions, {Posn,Elem} -> Elem



*Erik.               
> 



More information about the erlang-questions mailing list