Re: logical inconsistency in Union
- To: mathgroup at smc.vnet.net
- Subject: [mg13126] Re: [mg13069] logical inconsistency in Union
- From: Daniel Lichtblau <danl>
- Date: Tue, 7 Jul 1998 03:44:30 -0400
- References: <199807042045.QAA02915@smc.vnet.net.>
- Sender: owner-wri-mathgroup at wolfram.com
Veit Elser wrote:
>
> 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[3]:=
> approxSame[a,b]
>
> Out[3]=
> True
>
> In[4]:=
> approxSame[a,c]
>
> Out[4]=
> False
>
> In[5]:=
> Union[{a,b,c},SameTest->approxSame]
>
> Out[5]=
> {{1,1},{1.1,2},{1.2,1}} (* incorrect result ! *)
>
> In[7]:=
> Union[{a,b},SameTest->approxSame]
>
> Out[7]=
> {{1,1}} (* correct result *)
>
>
> To fix this problem we have to be allowed to modify the ordering
> function used by Union in order to be consistent with SameTest. An even
> better solution would be to be able to overide Mathematica's Order
> function (which returns -1,0,1). This would accomplish both: a
> consistent rule for sorting and a criterion to decide if two elements
> are the same.
>
> This problem affects other set theoretic functions as well (e.g.
> Complement).
>
>
>
> -Veit
I do not think overriding the ordering would help in cases where the
user-provided SameTest does not give a canonical ordering. About all
that can be done for Union et al is a brute-force comparison of every
candidate element with all elements already in the set under
construction.
This problem was noted by several people at the recent Worldwide
Mathematica Conference. I fixed it in our development version.
In[6]:= Union[{a,b,c},SameTest->approxSame] Out[6]= {{1, 1}, {1.1, 2}}
Daniel Lichtblau
Wolfram Research
- References:
- logical inconsistency in Union
- From: Veit Elser <ve10@cornell.edu>
- logical inconsistency in Union