Search All of the Math Forum:

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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

 Messages: [ Previous | Next ]
 Roman Maeder Posts: 8 Registered: 12/4/04
Re: prograMing: EquivalenceIndex
Posted: Mar 4, 1998 3:01 AM

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/
-----------------------------------------------------------------------

Date Subject Author
2/23/98 Xah Lee
3/2/98 Clemens Frey
3/3/98 Xah Lee
3/4/98 Roman Maeder
3/8/98 Roman Maeder