435,337 Members | 2,234 Online
Need help? Post your question and get tips & solutions from a community of 435,337 IT Pros & Developers. It's quick & easy.

# order a list depending on result of first ordered item.

 P: 5 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. Expand|Select|Wrap|Line Numbers 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) Oct 23 '15 #1

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.
Expand|Select|Wrap|Line Numbers
1. poly=[(36, 90), (91, 44), (47, 49), (33, 80)]
2.
3. ## [A, B, C, D] or[B, A, D, C] or[C, D, A, B]or[D, C, B, A]
4. order_list = [[0, 1, 2, 3], [1, 0, 3, 2], [2, 3 ,0, 1], [3, 2 ,1, 0]]
5.
6. ## find smallest
7. ## you could also use min and index
8. offset=0
9. for ctr in range(len(poly)):
10.     if poly[ctr][1] < poly[offset][1]:
11.         offset=ctr   ## location of smallest
12. print "smallest =", poly[offset]
13.
14. ## offset location of lowest corresponds to the item in the order_list
15. new_list=[]
16. for num in order_list[offset]:
17.     new_list.append(poly[num])
18. print new_list

8 Replies

 P: 16 can i see the code?? Oct 23 '15 #2

 Expert 100+ P: 621 And why reorder the list instead of using it as is? The code is simple enough, find the smallest element, and reorder Expand|Select|Wrap|Line Numbers 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]  Oct 23 '15 #3

 P: 5 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. Oct 23 '15 #4

 Expert 100+ P: 621 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 Expand|Select|Wrap|Line Numbers 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 Expand|Select|Wrap|Line Numbers 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  Oct 23 '15 #5

 P: 5 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. Oct 23 '15 #6

 Expert 100+ P: 621 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. Expand|Select|Wrap|Line Numbers 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  Oct 24 '15 #7

 P: 5 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! Oct 24 '15 #8

 P: 5 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: Expand|Select|Wrap|Line Numbers 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) Oct 24 '15 #9