# How to use Union on list of lists without sorting them first?

If I do

ClearAll[a, d]
lsts = {{a, d}, {a, d}};
Union[lsts]


{{a, d}}


but if I do

lsts = {{a, d}, {d, a}};
Union[lsts]


I get

{{a, d}, {d, a}}


Since I am using Union, I thought the order of the lists would not matter. Hence to get around this, now I always add Sort first, like this

lsts = {{a, d}, {d, a}};
Union[Sort /@ lsts]


and now I get expected answer

{{a, d}}


Question: Is this the right way to approach this? or do you recommend a better way?

• why is {{a,d}} the expected answer? I interpret lsts as a list of sets, which I want to join. So shouldn't it be {a,d}? Commented Jan 17, 2012 at 22:58
• sorry but what is the difference between this and Union @@ lsts? Commented Jan 17, 2012 at 23:00
• I see it. Agree with Leonid. Commented Jan 17, 2012 at 23:19

Sorting of sub-lists seems unavoidable since this is what brings them to a "canonical form" in this problem. If you don't care about the order of your resulting sub-lists, you could used DeleteDuplicates in place of Union though - this should be faster for large lists.

• Good call, I didn't think of that. And in fact DeleteDuplicates allows a custom equality test, so you could only sort the list in the test if you wanted your results in unsorted form. Commented Jan 17, 2012 at 23:06
• @David Be careful with these equality tests, they often lead to slowdowns which are not immediately obvious. For Union such custom-function-induced slowdowns will be much more severe though, see e.g. this discussion: mathprogramming-intro.org/book/node290.html Commented Jan 17, 2012 at 23:08
• True, I should have mentioned that a custom equality test could make the command significantly slower. Commented Jan 17, 2012 at 23:10
• Hmmm ... the example on mathprogramming-intro.org isn't even an equivalence relation. I'd expect all sorts of strange things to happen in such a case, and especially I'd not expect timings to be in any way representative for the timing you get with functions having the correct semantics. Commented Jan 18, 2012 at 12:00
• @celtschk Whenever any user-defined function is supplied (even when it happens to be a built-in), Union switches to quadratic-time algorithm based on pairwise comparisons. This is because Union accepts sameness function, not a comparison function (the existence of the latter is a stronger requirement). Whenever it is not specified, it so happens that SameQ (default) has an accompanying comparison function based on canonical sort, so it uses n*log n sorting then. I actually explained this in considerable detail in my post in that thread. Commented Jan 18, 2012 at 14:29

You can provide a custom SameTest to Union where you can take advantage of your knowledge what should qualify as equal, for example:

In[1] := Union[{{a,d},{d,a}}, SameTest -> (Complement[##] === {}&)]
Out[1] = {{a, d}}


It might be that you're slightly misunderstanding what Union does. It finds the union of the elements of the list that is passed to it, but it doesn't dig into lists within that list. So when you write Union[{{a,d},{a,d}}], the function sees a list with two elements, {a,d} (that's element 1) and {a,d} (that's element 2). They are the same, so it removes the duplicate and returns just {a,d}. But when you write Union[{{a,d},{d,a}}], it sees a list with two different elements: {a,d} (that's element 1) and {d,a} (that's element 2). The fact that those two lists contain the same items is irrelevant; they're not equal, according to an ordered element-by-element comparison, so Union has no duplicates to remove.

Now, it seems like what you're trying to do is get all lists which are distinct in terms of their content, irrespective of order - in other words, you're treating the lists as mathematical sets. I think Union[Sort/@lsts] should be a fine way to go, because that's the standard method of comparing sets for equality when you don't have an actual unordered set type. (If Mathematica does, I don't know about it.)

• If he wants to treat the lists as mathematical sets (i.e. also consider duplicates as irrelevant), then using Union also for sorting would be a better idea (because it removes duplicates). That is, for the list lsts={{a, b}, {a, b, b}}, Union[Sort/@lsts] will give lsts back, while Union[Union/@lsts] will give just {{a,b}}. Commented Jan 18, 2012 at 7:23

You could do the following:

lists = {{c, b, a}, {c, a, b}};
Union[lists, SameTest -> (Sort[#1] == Sort[#2] &)]


Note that the result is {c,a,b}, which is unsorted. The underlying algorithm can no longer take advantage of a linear comparison of the terms, however. As a result the time complexity is quadratic and will slow down your code considerably for very long lists. Thus, I'd advise against this approach. Ordering the lists first, as you've done, is preferable.

Your problem is reminiscent of the thing one has to do when dealing with noncommutative monomials.

Depending on the typical content of your lists (especially if you have a lot of strictly identical elements), it might be beneficial to apply Union twice, in this way

Union[ Sort/@(Union[ lst ]) ]

or

Union[ Union[ lst], SameTest -> (Equal[Sort[#1],Sort[#2]] &) ]

if you want to retain some of the diversity of the original instead of having everything mapped to a canonically sorted form.

The problem is more complex when you consider more deeply structured lists of course. You might end up with a very costly comparator function.

An object oriented approach would be to define for each object symbol a comparator function that would be called automatically as SameTest when a modified Union is called with arguments of a given head.

• In testing (which I admit was not comprehensive, but it did cover very small through very large lists), Union[Sort /@ lst] was consistently the fastest approach. I tried various combinations of DeleteDuplicates, Tally, Orderless functions, sequences of tests (e.g., test on Max and then sort), and even Hash. Commented Jan 18, 2012 at 0:53

To get rid of items that are duplicates under Sort you may use this:

GatherBy[lsts, Sort][[All, 1]]


Afterward you may sort or manipulate that list as you see fit.
Be warned that there is apparently a bug in Mathematica 7 with this specific code.

New in Mathematica 10:

DeleteDuplicatesBy[lsts, Sort]


I am not sure you are doing it right. Union expects a set per argument. As you only give it one argument, you are basically doing the union over one set A, which is incidentally A. What you want to do is Union @@ lsts which is Apply[Union,lsts]