MathGroup Archive 2000

[Date Index] [Thread Index] [Author Index]

Search the Archive

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}.


  • Prev by Date: Re: Thx for your help
  • Next by Date: integrity of ListContourPlot, ListDensityPlot
  • Previous by thread: RE: Re: parametricplot
  • Next by thread: Re: DeleteRepetitons and "functions" with memory