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