Re: logical inconsistency in Union
- To: mathgroup at smc.vnet.net
- Subject: [mg13109] Re: [mg13069] logical inconsistency in Union
- From: David Withoff <withoff>
- Date: Tue, 7 Jul 1998 03:44:13 -0400
- Sender: owner-wri-mathgroup at wolfram.com
> The Union function gives logically inconsistent results when used with
> certain SameTest rules. The problem is that the argument of Union is
> first sorted into Mathematica's canonical order, which may be
> inconsistent with the supplied SameTest. Here's an innocent example of
> the problem:
>
> In[1]:= (* 3 points in the plane *)
> a={1,1};
> b={1.2,1};
> c={1.1,2};
>
> In[2]:= (* rule which says two points are the same if each coordinate
> differs by at most 0.5 *)
> approxSame[x_,y_]:=Round[x-y]=={0,0}
>
> In[5]:=
> Union[{a,b,c},SameTest->approxSame]
>
> Out[5]=
> {{1,1},{1.1,2},{1.2,1}} (* incorrect result ! *)
This has been discussed a few times in mathgroup before, so you may be
able to find some useful information in the mathgroup archives. See
also the Wolfram Research web site:
http://www.wolfram.com/support/Kernel/Symbols/System/Union.html
It is likely that Union will be extended in a future version of
Mathematica so that it will work as you describe. Comparing all pairs
of elements is of course a lot slower for large sets than sorting and
comparing only adjacent pairs, which is why Union is designed as it is,
but sometimes there isn't much choice. In the meantime, until that
functionality is built in, it can be programmed into existing versions
of Mathematica without too much difficulty. One of the programs from
the Wolfram Research web site is
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]
]
but there are other ways to achieve the same effect.
Dave Withoff
Wolfram Research