Re: programming DeleteRepetitions Correction

• To: mathgroup at smc.vnet.net
• Subject: [mg23777] Re: [mg23662] programming DeleteRepetitions Correction
• From: "Allan Hayes" <hay at haystack.demon.co.uk>
• Date: Sat, 10 Jun 2000 02:59:23 -0400 (EDT)
• References: <8gv88o\$5n7@smc.vnet.net> <8hfegm\$hnf@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```Please change DF to DR in  the code in my previous posting - appologies for
the partial editing.

I have made this correction in the copy below.

-------
Bob,

The full list is {DR1, ...., DR9}

DR1 is a new version using Splot
DR2 is Carl Woll's code that I gave before (tidied up)
DR3 is a faster rewrite of your DeleteRepetitions1
The rest are your other examples reordered (your numbering is given against
the code).

In the timings:
test[r, n] gives the timings for  DR1, ...DRn  on a list of 1000 random
integers between 1 and r.

DR6, your DeleteRepetitions6, is fastest up to r = 20.

**TIMINGS**

test[2, 9]
{0.11, 0.06, 0., 0.22, 0.05, 0., 0.17, 0., 1.37}
test[10, 8]
{0.17, 0.05, 0.06, 0.22, 0.05, 0., 0.55, 0.}
test[20, 8]
{0.11, 0.05, 0.11, 0.22, 0.11, 0., 1.16, 0.16}
test[30, 8]
{0.1, 0.06, 0.11, 0.22, 0.11, 0.11, 1.49, 2.47}
test[40, 8]
{0.11, 0.05, 0.17, 0.38, 0.17, 0.16, 1.87, 4.28}
test[60, 6]
{0.11, 0.11, 0.22, 0.27, 0.22, 0.66}
test[100, 6]
{0.16, 0.06, 0.05, 0.49, 0.44, 0.61}
test[200, 6]
{0.11, 0.17, 0.11, 0.49, 0.94, 3.57}
test[400, 6]
{0.17, 0.27, 0.16, 0.94, 2.42, 4.99}
test[600, 6]
{0.16, 0.28, 0.22, 1.43, 3.79, 6.53}
test[1000, 6]
{0.16, 0.39, 0.33, 3.07, 5.93, 7.75}
test[1000000000000, 6] (*almost certainly no repetitions*)
{0.38, 0.55, 5.05, 5.28, 5.16, 5.33}

** CODE**

(*1*) ... (*6*)  indicateBob Hanlon's numbering.

Remove["`*"];

DR1[x_List] :=
Last[Transpose[
Sort[Reverse /@
First /@
Split[Sort[
Transpose[{x,
Range[Length[x]]}]], #1[[1]] == #2[[1]] &]]]];

DR2[x_List] := Block[{i}, i[n_] := (i[n] = Sequence[]; n);
i /@ x];

DR3[x_List] := x[[Sort[Flatten[First[Position[x, #]] & /@ Union[x]]]]];

(*2*)DR4[x_List] :=
Module[{uniq = {}},
If[Not[MemberQ[uniq, #]], (uniq = Append[uniq, #])] & /@ x;
uniq];
(*1*)DR5[x_List] :=
Take[x, #] & /@ Sort[First /@ (Position[x, #] & /@ Union[x])] //
Flatten;

(*6*)DR6[x_List] :=
Module[{uniq = Union[x], n, portion}, n = Length[uniq];
While[(Union[portion = Take[x, n]]) != uniq, n++];
Take[portion, #] & /@ Sort[First /@ (Position[portion, #] & /@ uniq)]
//
Flatten];

(*2*)DR7[x_List] :=
Transpose[
Union[Transpose[Join[{Range[Length[x]]}, {x}]],
SameTest -> (#1[[2]] == #2[[2]] &)]][[2]]

(*5*)DR8[x_List] :=
Module[{uniq = Union[x], n, portion}, n = Length[uniq];
While[(Union[portion = Take[x, n]]) != uniq, n++];
portion //. {a___, b_, c___, b_, d___} -> {a, b, c, d}]

(*4*)DR9[x_List] := x //. {a___, b_, c___, b_, d___} -> {a, b, c, d}

**TEST CODE**

funcs = ToExpression[Names["DF*"]]

{DR1, DR2, DR3, DR4, DR5, DR6, DR7, DR8, DR9}

SameQ @@ Through[funcs[Table[Random[Integer, {1, 10}], {100}]]]

True

test[r_, n_] :=
With[{lst = Table[Random[Integer, {1, r}], {1000}]},
Timing[#[lst]][[1]]/Second & /@ Take[funcs, n]]

-----------------

Allan
---------------------
Allan Hayes
Mathematica Training and Consulting
Leicester UK
www.haystack.demon.co.uk
hay at haystack.demon.co.uk
Voice: +44 (0)116 271 4198
Fax: +44 (0)870 164 0565

```

• Prev by Date: Solve this series