Union

Usage Message:

Attributes[Union] = {Flat, OneIdentity, Protected}

Options:

Notes:

Union sorts the elements before doing any comparisons, and treats elements as duplicates only if they appear in adjacent positions after sorting. Restricting the comparisons to adjacent elements allows the Union function to evaluate much more quickly (requiring time proportional to nlog(n) for a list of n elements) than if it compared all pairs of elements (which requires time proportional to n^2). This design does not affect the result using the default value of the SameTest option, but it can affect the result if the test specified by the SameTest option gives True for elements that are not sorted into adjacent positions.

(See below for examples of Union-like functions that compare all pairs of elements.)

Although the default comparison test in Union is equivalent to the test used by Order , the Order function is not called directly by Union, so changes to the definition of Order function will not affect the behavior of Union.

Various extensions to the current design of Union are being considered for future versions of Mathematica, including extensions to control sorting and way that comparisons are done.

It is relatively easy to implement alternate designs of Union. Here is an example of a function which compares all pairs of elements.

In[1]:= union1[p_List, test_] := Module[{result, link},
            result = link[];
            Scan[Module[{r=result}, 
                While[If[r===link[], result = link[result, #]; False,
                   !test[Last[r], #]], r = First[r]]] &, p];
            List @@ Flatten[result, Infinity, link]
        ]

In[2]:= data =  {f[1], g[1], h[2], f[2], h[3], g[2]} ;

In[3]:= test = Function[{x, y}, x[[1]] === y[[1]]] ;

In[4]:= union1[data, test]

Out[4]= {f[1], h[2], h[3]}

In[5]:= union1[Reverse[data], test]

Out[5]= {g[2], h[3], g[1]}

In[6]:= Union[data, SameTest -> test]

Out[6]= {f[1], f[2], g[1], g[2], h[3]}

In[7]:= union2[p_List, test_] := Module[{result, ei},
            result = {};
            Do[Catch[
                ei = p[[i]];
                Do[If[test[ei, result[[j]]],
                            Throw[Null]], {j, Length[result]}];
                AppendTo[result, ei]],
                {i, Length[p]}
            ];
            result
        ]

In[8]:= union2[data, test]

Out[8]= {f[1], h[2], h[3]}

It is possible with many comparison tests, including the test in this example, to take advantage of sorting to write a much faster function. The disadvantage of this method is that a different sorting function is required for each comparison test.

In[9]:= union3[p_List] := Module[{result, link},
            sp = Sort[p, Function[{x, y}, x[[1]] < = y[[1]]]];
            result = If[Length[sp] >  0, link[First[sp]], link[]];
            Do[If[sp[[i-1, 1]] =!= sp[[i, 1]],
                    result = link[result, sp[[i]]]], {i, 2, Length[sp]}];
            List @@ Flatten[result, Infinity, link]
        ]

In[10]:= union3[data]

Out[10]= {f[1], h[2], h[3]}