Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » Software » comp.soft-sys.math.mathematica

Topic: prograMing: EquivalenceIndex
Replies: 4   Last Post: Mar 8, 1998 5:06 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Roman Maeder

Posts: 8
Registered: 12/4/04
Re: prograMing: EquivalenceIndex
Posted: Mar 4, 1998 3:01 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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_] := OrderedQ[{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] := Map[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]:=First@FixedPoint[

With[{resultA=First@#,firstIndexes=#[[-1,1]],restIndexes=Rest@Las=
t@#,
firstPart=li[[#[[-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=Table[Random[Integer,{1,500}],{1000}];

Timing[r1=EquivalenceIndex[li];]

{4.95 Second,Null}

Timing[r2=ClassifyIndex[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. M=E4der 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/
-----------------------------------------------------------------------






Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.