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

```