order a list depending on result of first ordered item.

[SteveJLV]

Hello, My problem is to order a list (in my case 4 items) [A,B,C,D] all items are tuples i.e.(value1, value2)
we are looking for the element with the smallest value1.
This element has to become the first element in the ordered list, the rest of the list has to be one of the folowing :
[A, B, C, D] or[B, A, D, C] or[C, D, A, B]or[D, C, B, A]
So when C[0] had the smallest value1 the returned list should be in the order [C, D, A, B] independent of the values of the other elements.
I can get this result but the code looks very un-Pythonlike, and I have the feeling that this could be written in a clean way.

import random

random.seed()
poly = []
#the points are generated for purpose of explaining what I want to do
# in my actual program they are the cornerpoints of a polygone
for point in range(4):
    poly.append((random.randint(0,100), random.randint(0,100)))
# gives for instance - -> [(36, 90), (91, 44), (47, 49), (33, 80)]
print(poly)
#So now I have 4 points in a list [A,B,C,D], I want to rearange them.
# if for instance B[1] (= poly[1][1]) = 44 is the smallest from
#the 'X'[1] values then the points need to be arranged like [B, A, D, C]

# here is my solution, not so pretty...
polyAD = (poly[0], poly[3])
polyBC = (poly[1], poly[2])
polyCB = (poly[2], poly[1])
polyDA = (poly[3], poly[0])
polyAB = sorted((polyAD,polyBC), key = lambda pos: pos[0][1])
polyCD = sorted((polyCB,polyDA), key = lambda pos: pos[0][1])
polyABCD = sorted((polyAB,polyCD),key = lambda pos: pos[0][0][1])[0]
# now we have to put the second tuple at the back
poly =[polyABCD[0][0],polyABCD[1][0],polyABCD[1][1],polyABCD[0][1]]
# poly is now ordered as [ABCD],[BADC],[CDAB] or [DCBA]
print(poly)

[jaseel97]

can i see the code??

[dwblas]

And why reorder the list instead of using it as is? The code is simple enough, find the smallest element, and reorder

for record in a_list
    new_list.append(record[start:]+record[:start])
    etc
 
    or list comprehension
    new_list=[rec[start:]+rec[:start] for rec in old_list]

[SteveJLV]

The points in the list are the corners of a polygone, I am not looking to sort the points, just find the point with the smallest Y value and than arrange the points depending on which point has the smallest value. I put some code which ilustrates the idea.

[dwblas]

I understand this

So when C[0] had the smallest value1 the returned list should be in the order [C, D, A, B] independent of the values of the other elements.

and the idea posted, slicing, should work for this.

Using this as an example

# gives for instance - -> [(36, 90), (91, 44), (47, 49), (33, 80)]

I do not understand

# if for instance B[1] (= poly[1][1]) = 44 is the smallest from
#the 'X'[1] values then the points need to be arranged like [B, A, D, C]

not B, C, D, A which would be ordered by the smallest y values. B, A, D, C takes the smallest y value, and then orders the remaining 3 by the largest to the smallest.

To sort by the smallest y values

import operator

poly=[(36, 90), (91, 44), (47, 49), (33, 80)] 
s_list = sorted(poly, key=operator.itemgetter(1))
print s_list

And if you do want to sort the rest from largest to smallest, there are several ways. Python's Sorting Wiki

import operator

poly=[(36, 90), (91, 44), (47, 49), (33, 80)] 

## sort is simpliest way to find smallest
## and with only 4 items is also fast
s_list = sorted(poly, key=operator.itemgetter(1))
print s_list

small_large=[s_list[0]]  ## new list containing smallest
## slice off first element and sort remaining by highest
s_list_2 = sorted(poly[1:], key=operator.itemgetter(1),  reverse=True)
print s_list_2
small_large.extend(s_list_2)  ## extend list with sorted values
print small_large

[SteveJLV]

Dear dwblas, I do not want to sort the rest from the smallest to the largest. Please read the question I tried to make it clear, the sequence depends only on the el ement with the smallest value for one of its elements.

[dwblas]

So if A is the smallest, then is the order [A, B, C, D]. If B is the smallest then is the order [B, A, D, C]? You said it has to be one of the following, not why or when it is one of them so I have to guess, and this time am guessing that the lowest value comes first and determines the order. Also, I am assuming that the followng "C[0]" is a typo and you want the "y" or [1] offset in the sub_list, but the program can be easily changed if not.

So when C[0] had the smallest value1 the returned list should be in the order [C, D, A, B]

In any case this code should be able to be modified to do what you want, i.e. ordering a list according to the order stored in another list.

poly=[(36, 90), (91, 44), (47, 49), (33, 80)] 

## [A, B, C, D] or[B, A, D, C] or[C, D, A, B]or[D, C, B, A]
order_list = [[0, 1, 2, 3], [1, 0, 3, 2], [2, 3 ,0, 1], [3, 2 ,1, 0]]

## find smallest
## you could also use min and index
offset=0
for ctr in range(len(poly)):
    if poly[ctr][1] < poly[offset][1]:
        offset=ctr   ## location of smallest
print "smallest =", poly[offset]

## offset location of lowest corresponds to the item in the order_list
new_list=[]
for num in order_list[offset]:
    new_list.append(poly[num])
print new_list

[SteveJLV]

Thanks! The C[0] should be C[1] but that's not an issue. I' ll try to explain the why and when. As said the ABCD are points of a polygone in 2Dimensions. And I know that lines AB and CD do not cross and AC does not cross BD, I have a function in my program that takes a list with the polygons points in a specific order first the point with the lowest y - value, i.e. the bottom corner of my polygon the next two points of my list need to be the " neighbouring" points of this corner. I know that AB does not cross CD so when A has the smallest y-value it becomes poly[0] and B the next. So my list starts with AB BA CD or DC. From the knowledge that AC does not cross BD i can pick the third point. [0]=A -> [2]=C, [0]=C-> [2]A . The same goes for BD. Finaly the last point in the list is the oposing corner, which does not have to have a y-value greater than the other two points!

[SteveJLV]

figured it out. I realized that the points shift through the cycle in a specific way. It's easier to see when you put them in rows
[A B C D]
[B A D C]
[C D A B]
[D C B A] A and C shift from left to right and B and D shift one place to the left. When they fall off (left or right) they continue on the other side. So the new code looks like:

polypoints = [(33, 24), (0, 20), (32, 13), (28, 15)]
temppoints = [0,0,0,0]


def reorder(polypoints):
    direction = [1, -1, 1, -1]  
    lowest = min(polypoints, key =lambda y: y[1])[1]
    # cycle through untill first element has lowest 'y' value
    while polypoints[0][1] > lowest:
        # shift points to new configuration
        # ABCD -> BADC -> CDAB -> DCBA
        for i in range(4):
            # make shure the points cycle through when index is out of range
            temppoints[i] = polypoints[((i + direction[i])+4)%4]
        polypoints = temppoints[:] 
        # reverse shifting order
        direction = direction[::-1]
    return(polypoints)    

print(polypoints)
polypoints = reorder(polypoints)
print(polypoints)