On Saturday, August 1, 2015 at 1:34:44 PM UTC-7, Lukas Barth wrote:
> Hi!
>
> I have a list of numbers that I treat as "circular", i.e. [1,2,3] and [2,3,1]
> should be the same. Now I want to rotate these to a well defined status, so
> that I can can compare them.
>
> If all elements are unique, the solution is easy: find the minimum element,
> find its index, then use mylist[:index] + mylist[index:], i.e. the minimum
> element will always be at the beginning.
>
> But say I have [0,1,0,2,0,3]. I can in fact guarantee that no *pair* will
> appear twice in that list, i.e. I could search for the minimum, if that is
> unique go on as above, otherwise find *all* positions of the minimum, see
> which is followed by the smallest element, and then rotate that position to
> the front.
>
> Now that seems an awful lot of code for a (seemingly?) simple problem. Is
> there a nice, pythonic way to do this?
>
> Thanks for enlightening me!
[[[Warning: all code untested, sorry!]]]
The general problem (no assumptions about the items in the list except that
they're all sortable together) is interesting. It doesn't seem like a simple
one to me at all. An acceptable criterion would be if you took the lexically
smallest value of every rotation of the list; that would yield the same result
for every initial rotation. You can do it in like this:
anchor = min(range(len(X)),key=lambda i:X[i:]+X[:i])
canonical_X = X[anchor:]+X[:anchor]
I doubt this would be that efficient, though, since it happens to construct
every single rotation in the process of scanning. However, you'll notice that
the minimum lexical value can only occur when the starting point is the minimum
value in the list, so you can almost certainly improve performace to find all
the minimum values and only test those rotations, especially if the number of
minima is small compared to the list size. (However, be sure to timeit for
actual evidence rather than my guessing.)
min_value = min(X)
i = X.index(min_value)
while True:
start_points.append(i)
try:
i = X.index(min_value,i+1)
except ValueError:
break
anchor = min(start_points,key=lambda i:X[i:]+X[:i])
canonical_X = X[anchor:]+X[:anchor]
Your lists aren't arbitrary, however and they actually seem to be ordered pairs
(in which case the first question I have is why not have it be a list of
2-tuples? but I can imagine a few reasons). You say the pairs are known to be
unique, so all you have to do is find the index of the minimum pair. One can
use zip and slicing to generate 2-tuples from the flat list, whence you can
find the minimum.
pairs = list(zip(X[0::2],X[1::2]))
min_pair = min(pairs)
anchor = 2 * pairs.index(min_pair)
canonical_X = X[anchor:]+X[:anchor]
Carl Banks
--
https://mail.python.org/mailman/listinfo/python-list
