Re: Re: logical inconsistency in Union
- To: mathgroup at smc.vnet.net
- Subject: [mg13194] Re: [mg13109] Re: [mg13069] logical inconsistency in Union
- From: "Jrgen Tischer" <jtischer at col2.telecom.com.co>
- Date: Mon, 13 Jul 1998 07:42:43 -0400
- Sender: owner-wri-mathgroup at wolfram.com
Hi David,
this union1 is so awfully slow, so I tried to speed it up a bit. I
supposþd
that two elements are considered equal if they give the same result to a
criterion crit. My union4 is quite a bit faster even than union3 of
Union.html.
union4[p_List,crit_]:ÿdule[{result,link,new},
resultÿnk[];
new[_]ÿue;
Table[If[new[crit[p[[n]]]],new[crit[p[[n]]]]úlse;
resultÿnk[result,p[[n]]]],{n,Length[p]}];
List@@Flatten[result,\[Infinity],link]]
I hope you like it.
Jürgen
-----Original Message-----
From: David Withoff <withoff at wolfram.com> To: mathgroup at smc.vnet.net
Subject: [mg13194] [mg13109] Re: [mg13069] logical inconsistency in Union
>> 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};
>> bñ.2,1};
>> cñ.1,2};
>>
>> In[2]:ÿ* rule which says two points are the same if each coordinate
>> differs by at most 0.5 *)
>> approxSame[x_,y_]:ÿund[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_] :ÿodule[{result, link},
> result ÿink[];
> Scan[Module[{rþsult},
> While[If[rÿlink[], result ÿink[result, #]; False,
> !test[Last[r], #]], r ÿirst[r]]] &, p];
> List @@ Flatten[result, Infinity, link]
> ]
>
>but there are other ways to achieve the same effect.
>
>Dave Withoff
>Wolfram Research
>