# 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}? –  niklasfi Jan 17 '12 at 22:58
sorry but what is the difference between this and Union @@ lsts? –  Silvia Jan 17 '12 at 23:00
I see it. Agree with Leonid. –  Silvia Jan 17 '12 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. –  David Z Jan 17 '12 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 –  Leonid Shifrin Jan 17 '12 at 23:08
True, I should have mentioned that a custom equality test could make the command significantly slower. –  David Z Jan 17 '12 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. –  celtschk Jan 18 '12 at 12:00
@celtschk My bad - the first example doesn't hold water indeed. You are actually the first person to point it out - thanks. The other examples down that pages are ok though, I believe, and still illustrate my main point. I also discussed this problem here: forums.wolfram.com/mathgroup/archive/2009/Jul/msg00057.html, and in that thread there are other answers with good points. –  Leonid Shifrin Jan 18 '12 at 12:12

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}}. –  celtschk Jan 18 '12 at 7:23

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}}

-
+1, this is a very useful suggestion. –  rcollyer Jan 18 '12 at 4:11

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. –  whuber Jan 18 '12 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.

-

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]

-