MathGroup Archive 2007

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

Search the Archive

Re: ordered positions (OrderedPosition?)

  • To: mathgroup at smc.vnet.net
  • Subject: [mg83413] Re: ordered positions (OrderedPosition?)
  • From: Jean-Marc Gulliet <jeanmarc.gulliet at gmail.com>
  • Date: Tue, 20 Nov 2007 03:43:42 -0500 (EST)
  • Organization: The Open University, Milton Keynes, UK
  • References: <fhrrsj$5gh$1@smc.vnet.net>

Christian Chong-White wrote:

> I am wanting an elegant solution to find an ordering of elements of a
> set of nested lists at a specific level (the base level in this case
> but need not be). The output I am after is an ordered set of positions
> that references each of those elements in the original structure.
> 
> To explain: My ugly work-around was to flatten the nested list to get
> the ordering but this loses the structural information.
> 
> In[22]:= Ordering[
>  Flatten@{{4, 3, 3, 5, 1, 2, 5, 2, 3, 2}, {1, 5, 4, 1, 3, 4, 1, 7, 3,
> 4}}]
> 
> Out[22]= {5, 11, 14, 17, 6, 8, 10, 2, 3, 9, 15, 19, 1, 13, 16, 20, 4,
> 7, 12, 18}
> 
> The problem with the above is I have lost the information where in the
> structure the element was. I need the functionality of Position -
> including reference to depth, and Ordering.
> 
> Taking the above example further, what I am after is something like:
> {{1,5},{2,1}, etc}
> representing sorted positions of the original structure rather than
> {5,11, etc} of the flattened list.
> 
> It seems a very "Mathematica thing" I am after, and something that
> could well fit within an enhanced version of Ordering, but am lost at
> how to address the problem in a "Mathematica elegant manner."

The following function should do what you want efficiently and elegantly 
(I hope!)

In[1]:= myOrdering[lst_List] := Module[{struct},
   struct = Transpose[{Position[#, _Integer], Flatten[#]} &[data]];
   struct[[Ordering[struct, All, (#1[[-1]] <= #2[[-1]]) &], 1]]]

data = {{4, 3, 3, 5, 1, 2, 5, 2, 3, 2}, {1, 5, 4, 1, 3, 4, 1, 7, 3,
     4}};

myOrdering[data]

Out[3]= {{1, 5}, {2, 1}, {2, 4}, {2, 7}, {1, 6}, {1, 8}, {1, 10}, {1,
   2}, {1, 3}, {1, 9}, {2, 5}, {2, 9}, {1, 1}, {2, 3}, {2, 6}, {2,
   10}, {1, 4}, {1, 7}, {2, 2}, {2, 8}}

How does it work?
-----------------

We use Position to get the full path to each element.

In[4]:= Position[data, _Integer]

Out[4]= {{1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1,
   8}, {1, 9}, {1, 10}, {2, 1}, {2, 2}, {2, 3}, {2, 4}, {2, 5}, {2,
   6}, {2, 7}, {2, 8}, {2, 9}, {2, 10}}

Now we build a list of pairs, each pair contains a first element which 
is the path in the original structure and the second element which is 
the original value.

In[5]:= Transpose[{Position[#, _Integer], Flatten[#]} &[data]]

Out[5]= {{{1, 1}, 4}, {{1, 2}, 3}, {{1, 3}, 3}, {{1, 4}, 5}, {{1, 5},
   1}, {{1, 6}, 2}, {{1, 7}, 5}, {{1, 8}, 2}, {{1, 9}, 3}, {{1, 10},
   2}, {{2, 1}, 1}, {{2, 2}, 5}, {{2, 3}, 4}, {{2, 4}, 1}, {{2, 5},
   3}, {{2, 6}, 4}, {{2, 7}, 1}, {{2, 8}, 7}, {{2, 9}, 3}, {{2, 10},
   4}}

Finally, we use Ordering with three arguments, the last one being a 
custom test on the last element of each pair.

In[6]:= Ordering[
  Transpose[{Position[#, _Integer], Flatten[#]} &[
    data]], All, (#1[[-1]] <= #2[[-1]]) &]

Out[6]= {5, 11, 14, 17, 6, 8, 10, 2, 3, 9, 15, 19, 1, 13, 16, 20, 4, \
7, 12, 18}

We can see that the above result agrees with the original ordering.

In[7]:= Ordering[Flatten@data]

Out[7]= {5, 11, 14, 17, 6, 8, 10, 2, 3, 9, 15, 19, 1, 13, 16, 20, 4, \
7, 12, 18}

Regards,
-- 
Jean-Marc


  • Prev by Date: Neural networks with mathematica
  • Next by Date: Locator 3D
  • Previous by thread: Re: ordered positions (OrderedPosition?)
  • Next by thread: Re: ordered positions (OrderedPosition?)