Re: prograMing: EquivalenceIndex
- To: mathgroup@smc.vnet.net
- Subject: [mg11298] Re: prograMing: EquivalenceIndex
- From: Roman Maeder <maeder@mathconsult.ch>
- Date: Wed, 4 Mar 1998 01:39:54 -0500
- Organization: MathConsult Dr. R. Mdder
- References: <6dg483$2kb@smc.vnet.net>
for certain kinds of equivalence relations a much faster method exists.
If the relation sameQ[a, b] can be derived from a classifying function
f,
that is,
sameQ[a_,b_] :f[a] Ý f[b])
then we can derive a compatible ordering predicate orderedQ[a,b]:
orderedQ[a_, b_] :rderedQ[{f[a], f[b]}]
This can now be used to sort the input list (in time O[n Log[n]]) such
that only adjacent elements need to be compared with sameQ to split the
list into equivalence classes. There is even a function Split[] to do
this.
If no such compatible ordering predicate exists, bringing equivalent
elements close to each other seems much harder, and we are left with
one
of the given O[n^2] methods.
This program is a variant of Classify[] that was the topic of a
discussion in this group in 1995.
ClassifyIndex[li_List, f_:Identity] :ap[Last,
Split[Sort[Transpose[{f/@li,Range[Length[li]]}],
OrderedQ[{First[#1],First[#2]}]&],
First[#1] Ý First[#2]&], {2}]
If your equivalence predicate is SameQ, the corresponding function is
Identity, so in comparison with the the solution given in this group:
EquivalenceIndex[li_,sameTestQ_:SameQ]:òrst@FixedPoint[
With[{resultAòrst@#,firstIndexes;[-1,1]],restIndexes¾st@Last@#,
firstPartR[[#[[-1,1]]]]},
({Append[resultA,Join[{firstIndexes},Part[restIndexes,Flatten@#]]],
Delete[restIndexes,#]}&)@
Position[(sameTestQ[firstPart,#]&)/@Part[li,restIndexes],
True,{1}]
]&,
{{},Range@Length@li},
SameTest->(Last@#2Ý{}&)
];
we get:
liÚble[Random[Integer,{1,500}],{1000}];
Timing[r1êuivalenceIndex[li];]
{4.95 Second,Null}
Timing[r2ÅassifyIndex[li];]
{0.59 Second,Null}
Sort[r1]ÝSort[r2]
True
So, if your predicate is of this form, you can use the faster version.
Roman Maeder
-----------------------------------------------------------------------
MathConsult Dr. R. Maeder Samstagernstrasse 58a
Computer-Aided Mathematics 8832 Wollerau, Switzerland
T: +41-1-687 4051 mailto:maeder@mathconsult.ch
F: +41-1-687 4054 http://www.mathconsult.ch/
-----------------------------------------------------------------------