<div dir="ltr">If an "almost always works" solution is good enough, then sort on the distance to some fixed random point that is in the vicinity of your N points.<div><br></div><div>Jonathan</div></div><div class="gmail_extra">
<br><br><div class="gmail_quote">On Sun, Oct 27, 2013 at 3:51 PM, Freddie Witherden <span dir="ltr"><<a href="mailto:freddie@witherden.org" target="_blank">freddie@witherden.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="HOEnZb"><div class="h5">On 27/10/13 20:22, <a href="mailto:josef.pktd@gmail.com">josef.pktd@gmail.com</a> wrote:<br>
> On Sun, Oct 27, 2013 at 3:22 PM, Freddie Witherden<br>
> <<a href="mailto:freddie@witherden.org">freddie@witherden.org</a>> wrote:<br>
>> On 27/10/13 18:54, Daniele Nicolodi wrote:<br>
>>> On 27/10/2013 19:42, Freddie Witherden wrote:<br>
>>>> On 27/10/13 18:35, Nathaniel Smith wrote:<br>
>>>>> On Sun, Oct 27, 2013 at 6:28 PM, Freddie Witherden<br>
>>>>> <<a href="mailto:freddie@witherden.org">freddie@witherden.org</a>> wrote:<br>
>>>>>> Hi all,<br>
>>>>>><br>
>>>>>> This is a question which has been bugging me for a while. I have an (N,<br>
>>>>>> 3) array where N ~ 16 of points. These points are all unique and<br>
>>>>>> separated by a reasonable distance.<br>
>>>>>><br>
>>>>>> I wish to sort these points into a canonical order in a fashion which is<br>
>>>>>> robust against small perturbations. In other words changing any<br>
>>>>>> component of any of the points by an epsilon ~ 1e-12 should not affect<br>
>>>>>> the resulting sorted order.<br>
>>>>><br>
>>>>> I don't understand how this is possible even in principle.<br>
>>>>><br>
>>>>> Say your points are<br>
>>>>><br>
>>>>> a = [0, 0, 0]<br>
>>>>> b = [0, 0, 1e-12]<br>
>>>>><br>
>>>>> According to your criterion, either a or b should go first -- I don't<br>
>>>>> know which. Let's say our canonical ordering decides that a goes<br>
>>>>> first. But if you perturb both of them, then you have<br>
>>>>><br>
>>>>> a = [0, 0, 1e-12]<br>
>>>>> b = [0, 0, 0]<br>
>>>>><br>
>>>>> And now your requirement says that a still has to go first. But if a<br>
>>>>> goes first this time, then b had to go first the last time, by<br>
>>>>> symmetry. Thus your criterion is self-contradictory...?<br>
>>>><br>
>>>> Not exactly; in your case the distance between a and b is of the order<br>
>>>> epislon. However, my points are "all unique and separated by a<br>
>>>> reasonable distance." This requires at least one of the components of<br>
>>>> any two points to differ in all instances, permitting an ordering to be<br>
>>>> defined. (Where if epislon ~ 1e-12 the minimum instance between any two<br>
>>>> points is of order ~ 1e-6.)<br>
>>><br>
>>> Do you mean that all you points are distributed around some fixed points<br>
>>> in your space? In this case, it looks like what you are looking for is<br>
>>> categorization or clustering and not sorting. Once you perform<br>
>>> clustering, you can simply define an arbitrary order in which report the<br>
>>> content of each cluster. If this is not the case, the problem that<br>
>>> Nathaniel highlishts is still present.<br>
>><br>
>> I am not entirely sure what you mean here. If x is my array of points<br>
>> of size (16, 3) then I am guarenteeing that<br>
>><br>
>> np.min(scipy.spatial.distance.pdist(x)) >= 1e-6<br>
>><br>
>> In this instance I am unsure how the issue highlighted by Nathaniel<br>
>> might arise. Of course it is (very) possible that I am missing<br>
>> something, however, I believe under the terms of this constraint that it<br>
>> is always possible to define an order with which to iterate through the<br>
>> points which is invarient to shuffling of the points and small<br>
>> pertubations of the components.<br>
><br>
><br>
> If the epsilon or scale depends on the column, then, I think, divmod<br>
> should work to cut off the noise<br>
><br>
>>>> my_array[np.lexsort(divmod(my_array, [1e-1, 1e-12, 1])[0].T)]<br>
> array([[-0.5 , 0. , 1.41421356],<br>
> [ 0.5 , 0. , 1.41421356]])<br>
<br>
</div></div>An interesting proposal. However, it appears to have the same issues as<br>
the rounding approach. Consider:<br>
<br>
In [5]: a, b = 1.0 + 1e-13, 1.0 - 1e-13<br>
<br>
In [6]: abs(a - b) < 1e-12<br>
Out[6]: True<br>
<br>
In [7]: divmod(a, 1e-6)[0] == divmod(b, 1e-6)[0]<br>
Out[7]: False<br>
<br>
Hence should np.lexsort encounter such a pair it will consider a and b<br>
to be different even though they are within epsilon of one another.<br>
<br>
Regards, Freddie.<br>
<br>
<br>
<br>
<br>_______________________________________________<br>
NumPy-Discussion mailing list<br>
<a href="mailto:NumPy-Discussion@scipy.org">NumPy-Discussion@scipy.org</a><br>
<a href="http://mail.scipy.org/mailman/listinfo/numpy-discussion" target="_blank">http://mail.scipy.org/mailman/listinfo/numpy-discussion</a><br>
<br></blockquote></div><br></div>