Сравнение списка элементов

Question

У меня есть вопрос, и мне немного сложно его объяснить, поэтому я буду использовать множество примеров, чтобы помочь вам всем понять и посмотреть, сможете ли вы помочь мне.

Скажем, у меня есть два списка, содержащие названия книг от лучших до худших, оцененных двумя людьми. Пользователь1 получил оценку lstA, а пользователь2 получил оценку lstB

lstA = ['Harry Potter','1984','50 Shades','Dracula']
lstB = ['50 Shades','Dracula','1984','Harry Potter']

Пользователь считает, что «Гарри Поттер» лучше, чем «Дракула» (HP - индекс 0, а Дракула - индекс 3)

Пользователь два думает, что «Гарри Поттер» хуже Дракулы (HP - индекс 3, а Дракула - индекс 1)

В этом случае вернуть кортеж ('Harry Potter', 'Dracula') [('Dracula', 'Harry Potter') тоже нормально]

Пользователь один также оценил «50 оттенков» лучше, чем «Дракула», а второй пользователь также оценил «50 оттенков» лучше, чем «Дракула» (индексы 2, 3 и 0, 1 соответственно). В этом случае ничего не происходит.

Окончательный результат программы должен возвращать список кортежей так,

[('Harry Potter','50 Shades'), ('Harry Potter','Dracula'), ('Harry Potter','1984'), ('1984', '50 Shades'), ('1984','Dracula')]

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

Answer 1

Вы можете использовать iter, а затем сравнить индексы

res = []  

for i in lstA:
    a = iter(lstB)
    while True:
        try:
            b = next(a)
            if lstA.index(i) < lstA.index(b) and lstB.index(i) > lstB.index(b):
                res.append((i, b))
        except StopIteration:
            break 

print(res)
# [('Harry Potter', '50 Shades'), ('Harry Potter', 'Dracula'), ('Harry Potter', '1984'), ('1984', '50 Shades'), ('1984', 'Dracula')]

Answer 2

Эффективная версия решения @ jpp выглядит следующим образом:

from itertools import combinations

lstA = ['Harry Potter','1984','50 Shades','Dracula']
lstB = ['50 Shades','Dracula','1984','Harry Potter']

bIndices = {b: i for i, b in enumerate(lstB)}
aPairs = [sorted(c) for c in combinations(enumerate(lstA), 2)]

mismatches = [(book1[1], book2[1]) for book1, book2 in aPairs if bIndices[book1[1]] > bIndices[book2[1]]]
print(mismatches)
# [('Harry Potter', '1984'), ('Harry Potter', '50 Shades'), ('Harry Potter', 'Dracula'), ('1984', '50 Shades'), ('1984', 'Dracula')]

Обратите внимание, что aPairs - это комбинации (индекс, книга) кортежей, и каждая комбинация отсортирована по индексу, который гарантирует, что в каждой паре книг первая «лучше», чем следующая (для пользователя A).

Теперь, чтобы вычислить несоответствия порядка, нам просто нужно решить, будут ли соответствующие индексы книг в lstB также сохранять этот порядок.

Редактировать

Как отметил @MadPhysicist, combinations сохраняет исходный порядок в массиве в каждом сгенерированном кортеже, поэтому нет необходимости создавать aPairs как список отсортированных (index, book) кортежей. Мы можем напрямую генерировать mismatches с помощью bIndices:

lstA = ['Harry Potter','1984','50 Shades','Dracula']
lstB = ['50 Shades','Dracula','1984','Harry Potter']

bIndices = {b: i for i, b in enumerate(lstB)}
mismatches = [(book1, book2) for book1, book2 in combinations(lstA, 2) if bIndices[book1] > bIndices[book2]]

Answer 3

Один из способов сделать это состоит в том, чтобы собрать все положительные порядки из каждого списка в набор, а затем взять разность двух наборов. Положительный порядок будет (a, b), когда a предшествует b в соответствующем списке. Это заказ, гарантированный itertools.combinations:

from itertools import combinations

setA = set(combinations(lstA, 2))
setB = set(combinations(lstB, 2))

result = setA - setB

Это просто отбросило бы любые порядки, с которыми согласуются два набора. Если бы в обоих списках были одни и те же книги, это было бы почти идентично

result = setB - setA

Единственная разница будет в том, что все кортежи будут перевернуты.

Если бы в каждом списке были разные книги, вам нужно было бы добавить пару дополнительных шагов, чтобы очистить дубликаты и объединить два набора:

resultA = setA - setB
resultB = setB.difference(x[::-1] for x in setA)
result = resultA | resultB

На первом шаге вычисляются все элементы из lstA, с которыми lstB не согласен. Следующий шаг находит элементы lstB, которые не являются обращенными версиями того, что есть в resultA, поскольку разногласия по поводу книг в обоих списках гарантированно будут устранены в наборах. Я использовал метод set.difference здесь вместо оператора -, потому что таким образом нет необходимости создавать объект set из выражения генератора. Вы не можете просто использовать symmetric_difference / ^ к сожалению, потому что элементы обращены. Третий шаг просто вычисляет объединение результатов.

IDEOne Link: https://ideone.com/DuHTed. Это демонстрирует как оригинальный случай в вопросе, так и асимметричные списки.

Answer 4

Сначала сформулируйте свою логику математически. Для всех комбинаций длины 2 с учетом индексов idx_a1, idx_a2 и idx_b1, idx_b2, если sign(idx_a1 - idx_a2) != sign(idx_b1 - idx_b2), запишите комбинацию.

Ниже неэффективно, но он показывает один из способов преобразования этой логики в код:

from itertools import combinations

lstA = ['Harry Potter','1984','50 Shades','Dracula']
lstB = ['50 Shades','Dracula','1984','Harry Potter']

def sign(x):
    """Return +1 if integer is positive, -1 if negative"""
    return (x > 0) - (x < 0)

res = []
for a, b in combinations(lstA, 2):
    idx_a1, idx_a2 = lstA.index(a), lstA.index(b)
    idx_b1, idx_b2 = lstB.index(a), lstB.index(b)
    if sign(idx_a1 - idx_a2) != sign(idx_b1 - idx_b2):
        res.append((a, b))

[('Harry Potter', '1984'),
 ('Harry Potter', '50 Shades'),
 ('Harry Potter', 'Dracula'),
 ('1984', '50 Shades'),
 ('1984', 'Dracula')]