Sets vs Lists
- To: mathgroup at smc.vnet.net
- Subject: [mg8292] Sets vs Lists
- From: Andre Deprit <Deprit at his.com>
- Date: Sun, 24 Aug 1997 04:46:33 -0400
- Organization: Heller Information Services, Inc.
- Sender: owner-wri-mathgroup at wolfram.com
In his message [mg7953] How to select unique elements in a list?,
Carl Woll formulates more precisely what Gadi Oron had in mind.
After applying Union to a list L, one gets all the distinct elements of
L,
but ordered according Mathematica.
But Oron and Woll wants the distinct elements ordered they were in the
original list.
This preference can be given a precise mathematical meaning.
We say that x precedes y in the list L if
Min[Flatten[Position[L,x]]]<Min[Flatten[Position[L,y]]]
The solution proposed by Woll holds in the statements
RemoveDuplicates[a___, b_, c___, b_, d___]:=RemoveDuplicates[a, b,c, d]
Distinct[L_List]:=List@@RemoveDuplicates@@L
I tested it with the list
test=Join@@ Table[Reverse[majuscules],{50}]
where
majuscules={"A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P",
"Q","R","S","T","U","V","W","X","Y","Z"}
The result should be.Reverse[majuscules] where as Union[test]
===majuscules.
The computing time is of the order of 118.5 seconds on a
PowerBook3400-240.
I propose to solve the problem with the three instructions
distinct[L_List]:=distincT[L,{}]
distincT[{x_},z_]:=If[MemberQ[z,x],z,Append[z,x]]
distincT[{x_,y__},z_]:=
If[MemberQ[z,x],distincT[{y},z],distincT[{y},Append[z,x]]]
For the same test, the computing time is now of the order of 1.93
seconds.