By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
435,337 Members | 2,234 Online
Bytes IT Community
+ Ask a Question
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
  1. import random
  2.  
  3. random.seed()
  4. poly = []
  5. #the points are generated for purpose of explaining what I want to do
  6. # in my actual program they are the cornerpoints of a polygone
  7. for point in range(4):
  8.     poly.append((random.randint(0,100), random.randint(0,100)))
  9. # gives for instance - -> [(36, 90), (91, 44), (47, 49), (33, 80)]
  10. print(poly)
  11. #So now I have 4 points in a list [A,B,C,D], I want to rearange them.
  12. # if for instance B[1] (= poly[1][1]) = 44 is the smallest from
  13. #the 'X'[1] values then the points need to be arranged like [B, A, D, C]
  14.  
  15. # here is my solution, not so pretty...
  16. polyAD = (poly[0], poly[3])
  17. polyBC = (poly[1], poly[2])
  18. polyCB = (poly[2], poly[1])
  19. polyDA = (poly[3], poly[0])
  20. polyAB = sorted((polyAD,polyBC), key = lambda pos: pos[0][1])
  21. polyCD = sorted((polyCB,polyDA), key = lambda pos: pos[0][1])
  22. polyABCD = sorted((polyAB,polyCD),key = lambda pos: pos[0][0][1])[0]
  23. # now we have to put the second tuple at the back
  24. poly =[polyABCD[0][0],polyABCD[1][0],polyABCD[1][1],polyABCD[0][1]]
  25. # poly is now ordered as [ABCD],[BADC],[CDAB] or [DCBA]
  26. print(poly)
Oct 23 '15 #1

✓ answered by 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.
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 

Share this Question
Share on Google+
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
  1. for record in a_list
  2.     new_list.append(record[start:]+record[:start])
  3.     etc
  4.  
  5.     or list comprehension
  6.     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
  1. import operator
  2.  
  3. poly=[(36, 90), (91, 44), (47, 49), (33, 80)] 
  4. s_list = sorted(poly, key=operator.itemgetter(1))
  5. 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
  1. import operator
  2.  
  3. poly=[(36, 90), (91, 44), (47, 49), (33, 80)] 
  4.  
  5. ## sort is simpliest way to find smallest
  6. ## and with only 4 items is also fast
  7. s_list = sorted(poly, key=operator.itemgetter(1))
  8. print s_list
  9.  
  10. small_large=[s_list[0]]  ## new list containing smallest
  11. ## slice off first element and sort remaining by highest
  12. s_list_2 = sorted(poly[1:], key=operator.itemgetter(1),  reverse=True)
  13. print s_list_2
  14. small_large.extend(s_list_2)  ## extend list with sorted values
  15. 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
  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 
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
  1. polypoints = [(33, 24), (0, 20), (32, 13), (28, 15)]
  2. temppoints = [0,0,0,0]
  3.  
  4.  
  5. def reorder(polypoints):
  6.     direction = [1, -1, 1, -1]  
  7.     lowest = min(polypoints, key =lambda y: y[1])[1]
  8.     # cycle through untill first element has lowest 'y' value
  9.     while polypoints[0][1] > lowest:
  10.         # shift points to new configuration
  11.         # ABCD -> BADC -> CDAB -> DCBA
  12.         for i in range(4):
  13.             # make shure the points cycle through when index is out of range
  14.             temppoints[i] = polypoints[((i + direction[i])+4)%4]
  15.         polypoints = temppoints[:] 
  16.         # reverse shifting order
  17.         direction = direction[::-1]
  18.     return(polypoints)    
  19.  
  20. print(polypoints)
  21. polypoints = reorder(polypoints)
  22. print(polypoints)
Oct 24 '15 #9

Post your reply

Sign in to post your reply or Sign up for a free account.