Re: DeleteRepetitions summary
- To: mathgroup at smc.vnet.net
- Subject: [mg23806] Re: [mg23724] DeleteRepetitions summary
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Sat, 10 Jun 2000 03:00:12 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
It is of course true that Carl Woll's solution is neat and very ingenious but I think it is actually rather more than that. What is almost miraculous about it is that it seems to have a linear running time. To realize how remarkable this is it is enough to recall that fast sorting algorithms like quicksort generally have a running time of n*log(n). This means that assymptotically Carl's function is guaranteed to be faster than any one that uses sorting, which seems to include almost every other case. A pretty convincing explanation of how Carl's function manages to run in linear time was at the time when it first appeared given by Hartmut Wolf, so anyone interested in it can find it in the archive of this list. Andrzej Kozlowski -- Andrzej Kozlowski Toyama International University, JAPAN For Mathematica related links and resources try: <http://www.sstreams.com/Mathematica/> on 6/5/00 2:09 PM, Preston Nichols at pnichols at wittenberg.edu wrote > Greetings, > > Last week requested ideas for prgramming a function which extracts, in > order, the first instance of each distinct element of a list. > > Many thanks to Allan Hayes and David Park, who sent me Carl Woll's method > (so many thanks to Carl, too) and to Bob Hanlon, who documented (again) > Mathematica's power and flexibility by proposing five additional versions > of the function. > > > Here again is Carl Woll's solution: > > DeleteRepetitions[X_] := > Block[{t}, t[n_] := (t[n] = Sequence[]; n); t /@ X] > > Allan calls this a "neat solution", and David calls it a "very ingenious > routine"; I certainly agree. > > > I was also very happy to see Bob's > > DeleteRepetitions4[x_List] := x //. {a___, b_, c___, b_, d___} -> {a, b, c, d} > > because the code is so transparent, once you understand the simplest things > about pattern matching. That's a valuable feature in some contexts, even > though it is inefficient on long lists (as Bob pointed out). > > > In constrast, Carl's solution has a stunning "economy of action", but > understanding how it works requires thinking about such things as the > precedence of the operators := and ; (that's an operator?!), the internal > ordering of user-defined rules for functions, and the semi-magical > properties of Sequence[]. > > I intend to add both of these methods to my bag of tricks. I sure learn a > lot from this group! > > Preston Nichols > Mathematics and Computer Science > Wittenberg University > > > At 11:09 PM 05/28/2000 -0400, you wrote: >> Dear Mathematica Wizards: >> >> Below I give a function which removes duplicates from a list (as Union >> does), but without sorting the result (as Union also does). More >> specifically, it extracts, in order, the first instance of each distinct >> element of the list. >> >> Is there any simpler way to do this? It's a simple idea, but I seem to >> need seven different list-manipulation functions, including 3 uses of Map! >> >> DeleteRepetitions[X_] := >> Take[X, #] & /@ >> Sort[First /@ >> (Position[X, #] & /@ >> Union[X])] // Flatten >> >> For example, >> >> In[2] := DeleteRepetitions[{3,1,2,3,3,2,4,1}] >> >> Out[2] = {3,1,2,4} >> >> In[3] := DeleteRepetitions[{b,a,b,a,c,a}] >> >> Out[3] = {b,a,c} >> >> I don't need to use this function on lists longer that 20 or so elements, >> so speed is not a critical concern. >> >> Also, my version happens to work on expressions with heads other than List >> (because Take, Position, Union, and Flatten all do so), but I don't really >> need that feature. >> >> How would you implement this function? >> >> Preston Nichols >> Mathematics and Computer Science >> Wittenberg University >> > >