# Removing duplicates from a list

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

The list has the structure

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

-
Can we assume that the list is sorted such that duplicates would appear next to each other? That would simplify the task considerably. –  Christian Lindig Apr 26 '11 at 19:17
@Christian: I'm not sure it would: I'm intrigued to see how you'd implement a duplicate-removal approach. (The usual is simply to loop over the 'old' list and build a 'new' one with only the unique elements.) –  Joseph Wright Apr 26 '11 at 19:25
@Christian Lindig ...aha! Yes we can assume the list is sorted. –  Yiannis Lazarides Apr 26 '11 at 19:41
@Joseph Removing duplicates from an unsorted list takes quadratic effort but only linear effort for a sorted list. I still might not be sufficiently versed in TeX to express this idea. –  Christian Lindig Apr 26 '11 at 19:47
@Christian: But you have to sort it first :-) –  Joseph Wright Apr 26 '11 at 19:54

\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

-
Thanks, works fine. As is customary I will wait a bit and then accept the answer. –  Yiannis Lazarides Apr 26 '11 at 20:33
It's just a loop on all list elements; I'm no expert to tell if it's quadratic or worse. :) Of course, all list elements are assumed to be unexpandable, but one can think variations to cope with this case. –  egreg Apr 26 '11 at 20:40
I am not too sure either, but I just passed a list with about 5000 elements and it removed the duplicates before I could light a cigarette:) –  Yiannis Lazarides Apr 26 '11 at 20:51
adding elements one by one makes it quadratic, because each assignmnet will be linear in the size n of the clist, and you will end up doing it n times. Doing it linearly is more tricky, but feasible. –  Bruno Le Floch Apr 26 '11 at 21:00

I was inspired by Bruno's solution but I suggest to use only one full expandable pass. The main effect is reached by \expandafter\ifx\csname foo\endcsname\fi which expands to nothing but sets the \foo to \relax. This is only sole assignment done at expand processor level. All other assignments are done in main processor of TeX.

\def\noduplicate#1,{\ifx,#1,\else
\ifcsname dup:#1\endcsname
\else #1,\expandafter\ifx \csname dup:#1\endcsname \relax \fi
\fi
\expandafter\noduplicate \fi
}
\def\alist{john,mary,george,australia,australia,mary}

\edef\alist{\expandafter\noduplicate\alist,,}
\message{\meaning\alist}

\end


The e-TeX is needed because of \ifcsname is used. The string pool and hash table is (unfortunatelly) allocated but there is no way to deallocating them.

-
You can use grouping to prevent the allocation issue. –  yo' Jul 21 at 20:43
No. The meanig of control sequences are deallocated at the end of the group but string pool and hash table is not deallocated. –  wipet Jul 21 at 20:45

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:

\clist_new:N \l_my_clist
\clist_set: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

-
I get "Undefined control sequence" because \seq_elt:w is being expanded to \ERROR, which shouldn't happen. –  egreg Apr 26 '11 at 23:24
@egreg: that's because the internal implementation of l3seq changed recently. Let me add a line to fix that. –  Bruno Le Floch Apr 26 '11 at 23:30
@whomever was editing: sorry, I just saw it when clicking on the submit button. –  Bruno Le Floch Apr 26 '11 at 23:34
I should add that this method has a major drawback in that it can exhaust TeX's memory for control sequences (in my installation, when a comma-list reaches 60000 items or so), whereas some quadratic methods are less demanding on that kind of memory. –  Bruno Le Floch Apr 26 '11 at 23:55
In fact, it seems that even after closing a group, local definitions within it have already spent part of the hash size, which is not retrieved. If this is right, then it means that 60000 is the total number of items that can be treated in total in a given run. I'm not too sure about this, though. –  Bruno Le Floch Apr 27 '11 at 13:07

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

-