DeleteRepetitons and "functions" with memory

*To*: mathgroup at smc.vnet.net*Subject*: [mg23720] DeleteRepetitons and "functions" with memory*From*: Ranko Bojanic <rbojanic at columbus.rr.com>*Date*: Mon, 5 Jun 2000 01:09:14 -0400 (EDT)*Organization*: Ohio State University*Sender*: owner-wri-mathgroup at wolfram.com

The problem of finding a function DeleteRepetitons which removes duplicates from a list without sorting the result. was raised recently by Preston Nichols. For example, In[1] := DeleteRepetitions[{3,1,2,3,3,2,4,1}] Out[1] = {3,1,2,4} In[2] := DeleteRepetitions[{b,a,b,a,c,a}] Out[2] = {b,a,c} Preston's solution of this problem is DeleteRepetitions[X_] := Take[X, #] & /@ Sort[First /@ (Position[X, #] & /@ Union[X])] // Flatten Alan Hayes communicated a neat solution due to Carl Woll: DeleteRepetitions[X_] := Block[{t}, t[n_] := (t[n] = Sequence[]; n); t /@ X] Several other solutions were communicated by Bob Hanlon. I would like to try to explain here why and how Woll's elegant solution works. First, the "function" f defined by ClearAll[f] f[x_] := (f[x] = nil; x) has the following property: If a appears for the first time as an argument of f, we have f[a] = a. After that we always get f[a] = nil (Instead of nil we can put anything: {}, Sequence[],...) People more familiar with "functions" that have memory could probably say more about this definition. Then perhaps a satisfactory mathematical theory could be worked out. Before using this "function", we always have to erase it for obvious reasons from memory : In[3] := ClearAll[f] f[x_] := (f[x] = nil; x) Map[f,{3,1,2,3,3,2,4,1}] Out[3]= {3, 1, 2, nil, nil, nil, 4, nil} So to get the function DeleteRepetitions, we only have to remove nil prom this list. This can be done, for instance by writing In[4] := ClearAll[f] f[x_] := (f[x] = {}; x) Map[f,{3,1,2,3,3,2,4,1}] / /Flatten Out[4]= {3, 1, 2, 4} Here Map[f,{3,1,2,3,3,2,4,1}] produces the list {3,1,2,{},{},{},4,{}} which is flattened to {3, 1, 2, 4}. Using Sequence[] we can save this last step: In[5] := ClearAll[f] f[x_] := (f[x] = Sequence[]; x) Map[f,{3,1,2,3,3,2,4,1}] Out[5]= {3, 1, 2, 4} The reason for this is that Map[f,{3,1,2,3,3,2,4,1}] produces the set {3,1,2,Sequence[],Sequence[],Sequence[],4,Sequence[]} which flattens itself automatically into {3, 1, 2, 4}.