Removing duplicates from a list

Question

Is there a LaTeX kernel command to remove duplicates from a list?

The list has the structure

\def\alist{john,mary,george,australia,australia}

Answer 1

\makeatletter
\def\removeduplicates#1#2{\begingroup
  \let\@tempa#1%
  \def\@tempb{}%
  \@for\next:=\@tempa\do
    {\@ifundefined{lstel@\next}
      {\edef\@tempb{\@tempb,\next}
       \expandafter\let\csname lstel@\next\endcsname\@empty}
      {}%
    }%
  \edef\x{\endgroup\def\noexpand#2{\@tempb}}\x
  \expandafter\strip@comma#2\@nil#2}
\def\strip@comma,#1\@nil#2{\def#2{#1}}
\makeatother
\def\alist{john,mary,george,australia,australia,john}

\removeduplicates\alist\blist

\show\blist
\show\alist

\removeduplicates\alist\alist
\show\alist

When we look at each list element, say john, we see whether \lstel@john is undefined; in this case we add the list element to the new list and define the corresponding command. At the end we strip the initial comma. It doesn't work with an empty list, but adding that test is easy.

\removeduplicates can receive identical arguments, in this case the new list will overwrite the original one, of course.

Note: edited to avoid the use of \xdef

Answer 2

It is possible to remove duplicates in an almost linear time, without restriction on what the elements can be (except of course that they cannot contain commas without hiding them behind braces).

The hard thing is that adding elements one at a time would automatically lead to a quadratic time, since adding an element to a comma-list (or any token list in fact) takes a time proportional to the length of the list. So we somehow need to put all the elements at once.

Also, the only way that I can think of checking whether an item is a duplicate in an almost constant time is to define one control sequence per item. I am taking this idea from egreg's answer. The problem with that is that it regards as identical items which differ in their catcodes. To overcome this hurdle, we need a two-pass system:

• one step creates control sequences which contain a list of items for which \detokenize returns the same value;

• the other step puts all those control sequences together.

In both steps, we need to avoid duplicates, and it ends up being simpler to do the second step first, using the fact that \csname foo\endcsname lets \foo be \relax locally if it is undefined. The construction \ifcsname foo\endcsname \csname foo\endcsname \fi expands to \foo if it was undefined and lets it to \relax, otherwise it expands to nothing. By looping through the comma-list (using the expandable \clist_map_function:NN), we build a list of the form

\l_Xclist_<item1>_seq \l_Xclist_<item2>_seq ... \l_Xclist_<itemN>_seq

without duplicates.

In the second pass, we then define each of the \l_Xclist_<itemK>_seq. Each one of those is initially \relax, and we don't like this, so we test whether this is the case (with \if_meaning:w #1 \relax, which is simply \ifx), and if so, let them be an empty macro. Once we are sure that \l_Xclist_<itemK>_seq is a "good" sequence, we can use LaTeX3's seq macros to test whether (not detokenized) is in \l_Xclist_<itemK>_seq. If it is not, we add it.

At the end of the day, we have built all the \l_Xclist_<itemK>_seq, each containing a sequence of all the items which give <itemK> when detokenized. I then do something bad, reaching for the internals of the l3seq module by defining \seq_item:n, and doing essentially \xdef \g_Xclist_remove_clist {\g_Xclist_remove_clist}, which expands each sequence to the correct comma-list. The small \romannumeral subtelty is there to remove the first comma in a relatively cheap way.

\RequirePackage{expl3}
\ExplSyntaxOn
%
% Now we use a global clist to return the value.
% 
\clist_new:N \g_Xclist_remove_clist
%
% In the same way as in l3clist, we use a common auxiliary function
% for removing duplicates locally or globally.
%
\cs_new_protected_nopar:Npn \Xclist_remove_duplicates:N #1 {
  \Xclist_remove_duplicates_aux:N #1
  \clist_set_eq:NN #1 \g_Xclist_remove_clist
}
\cs_new_protected_nopar:Npn \Xclist_gremove_duplicates:N #1 {
  \Xclist_remove_duplicates_aux:N #1 
  \clist_gset_eq:NN #1 \g_Xclist_remove_clist
}
%
% The rough idea is to define one variable per element "#1"
% of the clist, and only add the element if the corresponding
% variable is not defined. 
% 
% with name "\g_clist_remove_\tl_to_str:n{#1}_seq",
% containing the sequence of all "#1" with the same detokenization.
% This is necessary to cater for the possibility that two different
% 
\cs_new_protected_nopar:Npn \Xclist_remove_duplicates_aux:N #1 
  {
    \group_begin:
    \tl_gset:Nx \g_Xclist_remove_clist 
      {
        \clist_map_function:NN #1 \Xclist_remove_duplicates_aux_ii:n
      }
    \clist_map_inline:Nn #1 
      {
        \exp_args:Nc \Xclist_remove_duplicates_aux_iii:Nn
        {l_Xclist_\tl_to_str:n{##1}_seq} {##1}
      }
    \cs_set:Npn \seq_item:n ##1 { , \exp_not:n {##1} }
    \cs_set:Npn\seq_elt:w##1\seq_elt_end:{\seq_item:n{##1}}%for older l3seq.
    \tl_gset:Nx \g_Xclist_remove_clist 
      { 
        \exp_after:wN \use_none:n \tex_romannumeral:D -`\0% remove leading ","
        \g_Xclist_remove_clist 
      }
    \group_end:
  }
\cs_new:Npn \Xclist_remove_duplicates_aux_ii:n #1 
  {
    \reverse_if:N \if_cs_exist:w l_Xclist_\tl_to_str:n {#1}_seq\cs_end:
      \cs:w l_Xclist_\tl_to_str:n{#1}_seq \cs_end:
    \fi:
  }
\cs_new:Npn \Xclist_remove_duplicates_aux_iii:Nn #1 #2
  {
    \if_meaning:w #1 \tex_relax:D
       \seq_clear:N #1
    \fi:
    \seq_if_in:NnF #1 {#2} {\seq_put_right:Nn #1 {#2}}
  }

A very basic test:

\tl_new:Nn \l_my_clist {a,b,c,d,e,\f,\g\h,a,b,c,\f,d,e,\g\h}
\clist_put_right:Nx \l_my_clist {\string a}
\clist_put_right:Nx \l_my_clist {\string b}
\clist_put_right:Nx \l_my_clist {\string c}
\clist_put_right:Nx \l_my_clist {\string d}
\clist_put_right:Nx \l_my_clist {\string e}

\clist_show:N \l_my_clist
\Xclist_remove_duplicates:N \l_my_clist
\clist_show:N \l_my_clist

Answer 3

The LaTeX2e kernel only provides \@removeelement, which will remove a specific element (and is used to remove class options from the global list). So you will need to either code your own or use a version pre-written in a package (for example \clist_remove_duplicates:Nn from expl3).