python - How to sort list of tuples based on variable in tuple

Question

Given a list of tuples in this format (item,[dependency, priority]) where the first element indicates an item, and the first element of the second indicates a dependency on a previously listed item(that means, the first item must appear in the list before the second item, on which it is dependent, appears), and finally a third element indicates the priority of rank for items of similar dependency. An example list looks like this:

[(1, [0, 4]),  
(2, [0, 3]),  
(3, [1, 4]),  
(4, [1, 1]),  
(5, [2, 4])]

I need a way to sort the list such that items for which the dependency has been satisfied can be ranked higher than items with a lower priority but with fewer or no dependencies.

For example, in the above list, the third item (3, [1, 4]) has a higher priority than the second item (2, [0, 3]), and so should be in the second position. The desired output of the example list should be this:

[(1, [0, 4]),  
(3, [1, 4]),  
(2, [0, 3]), 
(5, [2, 4]),
(4, [1, 1])]

I cannot simply sort by priority as that would elevate the fifth item 5, [2, 4]) to a spot above its dependency, which is 2.

So my idea was to iterate through the list, grouping all items for which a dependency is satisfied. Then sort that list by priority. Then recombine all resulting lists back into a single list.

I cannot figure out how to do this. My best attempt was something like this below. with dependency as n. but it only really works for the first iteration. When the dependency is higher than one, it returns all items. I suspect this is not the best strategy to accomplish the desired result.

Any ideas or suggestions would be appreciated!

    def rank_poss(array,n):
      final = []
      slot_list = []
      for i in array:
          if i[1][0] <= n and i[0] != 1:
              slot_list.append(i)  
      temp = sorted(slot_list, reverse=True, key = lambda x: x[1][2])
      final.append(temp)
      return final 

Answer 1

I don't know if I correctly understand your rules so I don't know if I get correct result.

In older Python you could use sorted (and few other functions) with argument cmp= to assign function which gets two items from list, compare them and return 0 when they are the same, -1 when first should be before second, 1 when second should be before first.

New Pythons don't have this argument but the is function functools.cmp_to_key() which should help to work like with old cmp= and then you may try to create more complex method to sort items.

data = [
    (1, [0, 4]),  
    (2, [0, 3]),  
    (3, [1, 4]),  
    (4, [1, 1]),  
    (5, [2, 4])
]

import functools
    
def compare(a, b):
    if a[1][0] >= b[0]:
        return 1
    if a[1][1] > b[1][1]:
        return -1
    return 1

result = sorted(data, key=functools.cmp_to_key(compare))
     
for item in result:
    print(item)

Result:

(1, [0, 4])
(3, [1, 4])
(2, [0, 3])
(5, [2, 4])
(4, [1, 1])