Блог

Дан список кортежей в этом формате (item,[dependency, priority]), где первый элемент указывает на элемент, а первый элемент второго указывает на зависимость от ранее перечисленного элемента (это означает, что первый элемент должен появиться в списке перед вторым элементом, на котором онзависит, появляется), и, наконец, третий элемент указывает приоритет ранга для элементов с аналогичной зависимостью. Пример списка выглядит следующим образом:

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

Мне нужен способ сортировки списка таким образом, чтобы элементы, для которых была удовлетворена зависимость, могли быть ранжированы выше, чем элементы с более низким приоритетом, но с меньшим количеством зависимостей или без них.

Например, в приведенном выше списке третий элемент (3, [1, 4]) имеет более высокий приоритет, чем второй элемент (2, [0, 3]), и так должно быть на второй позиции. Желаемый результат примера списка должен быть таким:

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

Я не могу просто отсортировать по приоритету, так как это повысило бы пятый элемент 5, [2, 4]) на место над его зависимостью, которое равно 2.

Итак, моя идея состояла в том, чтобы перебирать список, группируя все элементы, для которых удовлетворяется зависимость. Затем отсортируйте этот список по приоритету. Затем рекомбинируйте все результирующие списки обратно в один список.

Я не могу понять, как это сделать. Моя лучшая попытка была чем-то вроде этого ниже. с зависимостью как n. но это действительно работает только для первой итерации. Когда зависимость больше единицы, она возвращает все элементы. Я подозреваю, что это не лучшая стратегия для достижения желаемого результата.

Любые идеи или предложения будут оценены!

 
    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 

 

Я не знаю, правильно ли я понимаю ваши правила, поэтому я не знаю, получаю ли я правильный результат.

В более старом Python вы могли бы использовать sorted (и несколько других функций) с аргументом cmp= для назначения функции, которая получает два элемента из списка, сравнивает их и возвращает 0 , когда они совпадают, -1 когда первый должен быть перед вторым, 1 когда второй должен быть перед первым.

У новых Python нет этого аргумента, но есть функция functools.cmp_to_key(), которая должна помочь работать как со старыми cmp= , а затем вы можете попытаться создать более сложный метод для сортировки элементов.

 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)
 

Результат:

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