List comparison of element

Question

I have a question and it is a bit hard for me to explain so I will be using lots of examples to help you all understand and see if you could help me.

Say I have two lists containing book names from best to worst rated by two people. User1 rated lstA, and user2 rated lstB

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

User one thinks 'Harry Potter' is better than 'Dracula' (HP is index 0, and Dracula is index 3)

User two thinks 'Harry Potter' is worse than Dracula, (HP is index 3 and Dracula is index 1)

In this case, return a tuple ('Harry Potter', 'Dracula') [('Dracula', 'Harry Potter') is also fine]

User one also rated '50 shades' better than 'Dracula' and user two also rated '50 shades' better than 'Dracula' (index 2, 3 and 0, 1 respectively). In this case, nothing happens.

The final result of the program should return a list of tuples so,

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

Could someone help me to point me in the right direction to come up with an algorithm that gives all the tuples?

Answer 1

First formulate your logic mathematically. For all combinations of length 2, given indices idx_a1, idx_a2 and idx_b1, idx_b2, if sign(idx_a1 - idx_a2) != sign(idx_b1 - idx_b2), record the combination.

The below isn't efficient, but it shows one way of transforming this logic to code:

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')]

Answer 2

One way to do this would be to accumulate all the positive orderings form each list into a set, then take the difference of the two sets. The positive ordering would be (a, b) when the a precedes b in its respective list. This is the ordering guaranteed by itertools.combinations:

from itertools import combinations

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

result = setA - setB

This would simply discard any orderings that the two sets agree on. If both lists had the same books, this would be almost identical to

result = setB - setA

The only difference would be that all the tuples would be reversed.

If you had different books in each list, you would need to add a couple of extra steps to clean up the duplicates and combine the two sets:

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

The first step computes all the elements from lstA that lstB does not agree with. The next step finds the elements of lstB that aren't reversed versions of what we have in resultA, since the disagreements over books in both lists are guaranteed to be reversed in the sets. I used the method set.difference here in preference to the - operator because that way there is no need to create a set object from the generator expression. You can't just use symmetric_difference/^ unfortunately because the elements are reversed. The third step just computes the union of the results.

IDEOne Link: https://ideone.com/DuHTed. This demos both the original case in the question and the asymmetric lists.