Re: sorting a nested list of 4-tuples
- To: mathgroup at smc.vnet.net
- Subject: [mg120399] Re: sorting a nested list of 4-tuples
- From: Ray Koopman <koopman at sfu.ca>
- Date: Thu, 21 Jul 2011 05:48:16 -0400 (EDT)
- References: <j03o4c$a64$1@smc.vnet.net>
On Jul 19, 4:00 am, Luis Valero <luis.val... at mac.com> wrote:
> Dear Sirs,
>
> I want to sort a list of 4-tuples of real numbers, so that, the second 4-tuple has minimum distance to the first, the third, selected from the rest, ha minimum distance to the second, and so on.
>
> The distance is the euclidean distance, calculated with the first two elements of each 4-tuple.
>
> I have defined a function that work:
>
> orderedList[list_] := Module[{nearest},
> Flatten[ Nest[{
> Append[ #[[1]] , nearest = Flatten @@ Nearest[ Map[ Rule[ #[[{1, 2}]], #] &, #[[2]] ], Last[ #[[1]] ] [[{1, 2}]], 1] ],
> Delete[ #[[2]], Position[ #[[2]], nearest ] ] } &, { {list[[1]] }, Delete[ list, 1 ] }, Length[ list ] - 2], 1] ];
>
> but I need to improve the temporal efficiency
>
> Thank you
This does the job nicely without Nearest. For your real data,
change DistanceMatrix@xy to DistanceMatrix[list[[All,{1,2}]]].
n = 10
xy = Table[Random[Real],{n},{2}]
ddx = 2 Max[dd = DistanceMatrix@xy];
Do[dd[[i,i]] = ddx,{i,n}];
ddx = Table[ddx,{n}];
NestList[(dd[[#]] = ddx;
Ordering[dd[[All,#]],1][[1]])&, 1, n-1]
10
{{0.923827,0.822223}, {0.369167,0.352365},
{0.309981,0.792447}, {0.375829,0.953723},
{0.680294,0.594137}, {0.411011,0.098692},
{0.295584,0.0860474},{0.749339,0.927127},
{0.263566,0.0431098},{0.0684959,0.230974}}
{1,8,5,2,6,7,9,10,3,4}