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