Ранжирование элементов в другом списке

Question

У меня есть 3 списка, как показано ниже:

List 1  List 2  List 3
A       A       D
D       D       M
GE      M       A
G       G       S
M       S       G
S       GE     GE

Теперь мне нужно получить ранжирование элементов в списке путем усреднения ранга элементов по списку, как объяснено ниже:

Elements    Rank-List1  Rank-List2  Rank-List3  Average     Ranking
A               1           1           3        1.67          1
D               2           2           1        1.67          2
GE              3           6           6        5             5
G               4           4           5        4.33          4
M               5           3           2        3.33          3
S               6           5           4        5             6

В случае совпадения в среднем, выберите первый элемент как более высокий ранг.

Таким образом, окончательный список вывода будет:

Output list
A
D
M
G
GE
S

Среднее значение рассчитывается как Average = Sum of Rank (over all lists) / 3:

( 1+1+3) / 3 = 1.67 # for A 

Может ли это быть достигнуто программно в Python?

Answer 1

Вы можете попробовать вот так.

>>> import numpy as np
>>> import pandas as pd
>>>
>>> elements = ["A", "D", "GE", "G", "M", "S"]
>>> rank_list1 = [1, 2, 3, 4, 5, 6]
>>> rank_list2 = [1, 2, 6, 4, 3, 5]
>>> rank_list3 = [3, 1, 6, 5, 2, 4]
>>>
>>> df = pd.DataFrame({
...     "Elements": elements,
...     "Rank-List1": rank_list1,
...     "Rank-List2": rank_list2,
...     "Rank-List3": rank_list3,
... })
>>>
>>> df
  Elements  Rank-List1  Rank-List2  Rank-List3
0        A           1           1           3
1        D           2           2           1
2       GE           3           6           6
3        G           4           4           5
4        M           5           3           2
5        S           6           5           4
>>>
>>> df["Average"] = df.apply(lambda s: s[1:].mean(), axis=1)
>>> df
  Elements  Rank-List1  Rank-List2  Rank-List3   Average
0        A           1           1           3  1.666667
1        D           2           2           1  1.666667
2       GE           3           6           6  5.000000
3        G           4           4           5  4.333333
4        M           5           3           2  3.333333
5        S           6           5           4  5.000000
>>>
>>> df["Average"] = df.apply(lambda s: s[1:].mean().round(2), axis=1)
>>> df
  Elements  Rank-List1  Rank-List2  Rank-List3  Average
0        A           1           1           3     1.67
1        D           2           2           1     1.67
2       GE           3           6           6     5.00
3        G           4           4           5     4.33
4        M           5           3           2     3.33
5        S           6           5           4     5.00
>>>
>>> out = df.sort_values(by="Average")
>>> out
  Elements  Rank-List1  Rank-List2  Rank-List3  Average
0        A           1           1           3     1.67
1        D           2           2           1     1.67
4        M           5           3           2     3.33
3        G           4           4           5     4.33
2       GE           3           6           6     5.00
5        S           6           5           4     5.00
>>>
>>> out.Elements
0     A
1     D
4     M
3     G
2    GE
5     S
Name: Elements, dtype: object
>>>
>>> out.Elements.tolist()
['A', 'D', 'M', 'G', 'GE', 'S']
>>>

Answer 2

Оптимизированная версия решения Tomothys :

отсортировано (list1, ключ = лямбда-элемент: сумма ([list1.index (элемент), list2.index (элемент), list3.index (элемент)]) / 3)

вызывает .index() 3 раза для каждого элемента list1 - каждый вызов повторяет соответствующий список (для каждого элемента в list1), пока не найдет событие - в итоге вы получите что-то вроде sum([1,2,3,4,5,6]) три раза, что 63 (вместо 18 - см. Ниже).

Сложность моего решения определяется O(n), где n = sum(len(item) for item in data) => 18 - сложность сортировки незначительна, поскольку она работает только с set() элементов во всех списках, что намного меньше. сложность Timsort потребности (наихудший случай) O(m*log(m)) где m = set(i for sub in data for i in sub) => 6

---

from collections import defaultdict

data = [['A', 'D', 'GE', 'G', 'M', 'S'], ['A', 'D', 'M', 'G', 'S', 'GE'],
        ['D', 'M', 'A', 'S', 'G', 'GE']]

d = defaultdict(list) # or int and use /3.0 implicitly

# this loop touches each element once:  O(n) n = sum(length of all lists)
for l in data:
    for idx,value in enumerate(l):
        d[value].append(idx)

# timsort: O(m) to O(m*log(m)) for the much shorter set() over emelents of all lists)  
# sort by score:
result = sorted(d.items(), key= lambda x:sum(x[1])/float(len(x[1]))) 
print( *(r  for r in result), sep="\n") # use 'r[0] for r ..' to just print the names

Выход:

('A', [0, 0, 2])
('D', [1, 1, 0])
('M', [4, 2, 1])
('G', [3, 3, 4])
('GE', [2, 5, 5])
('S', [5, 4, 3])

---

Если вы гарантируете, что каждый подсписок содержит одинаковые элементы - просто в другом порядке, вы можете еще больше упростить:

d = defaultdict(int) 

# this loop touches each element once:  O(n)
for l in data:
    for idx,value in enumerate(l):
        d[value]+=idx

# there is no sense in dividing the sum by 3 if _all_ sums have to be devided by it

# sort by score:
result = sorted(d.items()) 
print( *(r  for r in result), sep="\n")  

Выход:

('A', 2)
('D', 2)
('G', 10)
('GE', 12)
('M', 7)
('S', 12)

---

defaultdict быстрее, чем обычные диктовки - но если вы не любите импортировать, вы можете изменить его на более медленный

d = {}
d.setdefault(key, []).append(value)  # defaultdict(list)
d.setdefault(key, 0) += value      # defaultdict(int)

setdefault(key,default) медленнее, потому что он всегда создает default, что требует времени - defaultdict (...) оптимизирован, чтобы не нуждаться в этом, и поэтому (немного) быстрее.

Answer 3

Использование аргумента key функции sorted:

list1 = ['A', 'D', 'GE', 'G', 'M', 'S']
list2 = ['A', 'D', 'M', 'G', 'S', 'GE']
list3 = ['D', 'M', 'A', 'S', 'G', 'GE']

sorted(list1, key=lambda elem: sum([list1.index(elem), list2.index(elem), list3.index(elem)]) / 3)

Или, для списка списков:

lists = [['A', 'D', 'GE', 'G', 'M', 'S'],
         ['A', 'D', 'M', 'G', 'S', 'GE'],
         ['D', 'M', 'A', 'S', 'G', 'GE']]

sorted(lists[0], key=lambda elem: sum(sublist.index(elem) for sublist in lists) / len(lists))

Вывод для обоих случаев выше:

['A', 'D', 'M', 'G', 'GE', 'S']