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