Re: Q: how to rank a list of elements?
- To: mathgroup at smc.vnet.net
- Subject: [mg23161] Re: [mg23105] Q: how to rank a list of elements?
- From: Hartmut Wolf <hwolf at debis.com>
- Date: Thu, 20 Apr 2000 23:48:36 -0400 (EDT)
- Organization: debis Systemhaus
- References: <200004190630.CAA07457@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Dear Wen-Feng,
Wen-Feng Hsiao schrieb:
>
> I would like to obtain the ranking of a list of elements. So I conduct
> the following procedure:
>
> In[60]:=
> pseudo = {15, 7, 15, 1}
> pseudoSort = pseudo // Sort
> ranks = Position[pseudoSort, #] & /@ pseudo
> rmDuplicate[ranks] // Flatten
>
> Out[60]=
> {15, 7, 15, 1}
> Out[61]=
> {1, 7, 15, 15}
> Out[62]=
> {{{3}, {4}}, {{2}}, {{3}, {4}}, {{1}}}
> Out[63]=
> {3, 2, 4, 1}
>
> However, there are two questions: 1) the ranking is not quite correct, in
> which the tie situation is not addressed well in my procedure.
Since you didn't state your problem but only a solution, it's hard to
guess. (It would have been helpful to have stated the "real world
problem"; often the mapping of that to the mathematical model -- or
object model for programming -- is the most decisive step to a
solution.)
Anyways, you have to answer yourself the question: why not have
{4, 2, 3, 1} or
{3, 2, 3, 1} or even
{{3, 4}, 2, {3, 4}, 1} or
{{3, 4}, 2, see[1], 1}
as a result?? (It also depends on what you intend to do with it.)
> ... Is
> there any system defined function for this purpose?
sic!
> ... And, 2) the function
> rmDuplicate is written in procedural way, i.e., using For to remove
> duplicated elements, could someone help/show me using functional or rule
> way to design this function?
¿what is rmDuplicate? If you like to have advice on programming in
style, performance, correctness,... you should show your prog.
I'll give you some suggestions, if you like to check them for your
problem:
(1) With tribute to Carl Woll:
In[1]:= disamb[ranks_] :=
(i[{}] = {};
i[p_] := (With[{succ = Rest[p]}, i[p] := i[succ]]; First[p]);
i /@ ranks // Flatten)
In[2]:= disamb[{{{3}, {4}}, {{2}}, {{3}, {4}}, {{1}}}]
Out[2]= {3, 2, 4, 1}
In[3]:= ?i
i[{}] = {}
i[{{1}}] := i[{}]
i[{{2}}] := i[{}]
i[{{4}}] := i[{}]
i[{{3}, {4}}] := i[{4}]
i[p_] := (With[{succ = Rest[p]}, i[p] := i[succ]]; First[p])
In[4]:= Clear[i]
To use this for production enclose the rhs of the definition for disamb
with Block[{i}, ...], then you also don't need to Clear[i] after each
run. You also might wish to test this with more demanding test cases.
(2) observe the sequence of steps:
In[7]:= {15, 7, 15, 1};
In[8]:= Transpose[{%, Range[Length[%]]}]
Out[8]= {{15, 1}, {7, 2}, {15, 3}, {1, 4}}
In[9]:= Sort[%]
Out[9]= {{1, 4}, {7, 2}, {15, 1}, {15, 3}}
In[10]:= Transpose[{Last[Transpose[%]], Range[Length[%]]}]
Out[10]= {{4, 1}, {2, 2}, {1, 3}, {3, 4}}
In[11]:= Sort[%]
Out[11]= {{1, 3}, {2, 2}, {3, 4}, {4, 1}}
In[12]:= Last[Transpose[%]]
Out[12]= {3, 2, 4, 1}
So this algorithm is of time complexity O(n log n) as should be your
procedure if you use daDuplicate (I can't say anything about
rmDuplicate). You also might get an idea for an efficient implementation
of Position.
(3) You can also solve the entire problem in linear time O(n), at the
cost of space (Carl Woll style):
In[13]:= len = Length[{15, 7, 15, 1}];
In[14]:=
c = 0;
dig[obj_] := (\[Rho][obj, ++c] = Null);
dig /@ {15, 7, 15, 1};
In[17]:= digged = Extract[#, {1, 1}, Hold] & /@ DownValues[\[Rho]]
Out[17]=
{Hold[\[Rho][1, 4]], Hold[\[Rho][7, 2]],
Hold[\[Rho][15, 1]], Hold[\[Rho][15, 3]]}
In[18]:=
c = 0;
dig[Hold[\[Rho][obj_, p_]]] := (\[Xi][p] = ++c);
dig /@ digged;
In[21]:= Array[\[Xi], {len}]
Out[21]= {3, 2, 4, 1}
In[22]:= Clear[\[Rho], \[Xi]]
Kind regards, Hartmut
- References:
- Q: how to rank a list of elements?
- From: d8442803@student.nsysu.edu.tw (Wen-Feng Hsiao)
- Q: how to rank a list of elements?