Mixing
List comparison of element
Clash Royale CLAN TAG#URR8PPP
up vote
6
down vote
favorite
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?
python list sorting
edited 1 hour ago
Mad Physicist
31.5k156490
asked 2 hours ago
Michael
362
add a comment |Â
up vote
6
down vote
favorite
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?
python list sorting
edited 1 hour ago
Mad Physicist
31.5k156490
asked 2 hours ago
Michael
362
You might want to take a look at this link geeksforgeeks.org/counting-inversions It does precisely what you are looking for.
– Anurag A S
2 hours ago
Thank you I will take a look!
– Michael
2 hours ago
add a comment |Â
up vote
6
down vote
favorite
up vote
6
down vote
favorite
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?
python list sorting
edited 1 hour ago
Mad Physicist
31.5k156490
asked 2 hours ago
Michael
362
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?
python list sorting
python list sorting
edited 1 hour ago
Mad Physicist
31.5k156490
asked 2 hours ago
Michael
362
edited 1 hour ago
Mad Physicist
31.5k156490
asked 2 hours ago
Michael
362
edited 1 hour ago
Mad Physicist
31.5k156490
edited 1 hour ago
Mad Physicist
31.5k156490
edited 1 hour ago
Mad Physicist
31.5k156490
31.5k156490
asked 2 hours ago
Michael
362
asked 2 hours ago
Michael
362
asked 2 hours ago
Michael
362
362
You might want to take a look at this link geeksforgeeks.org/counting-inversions It does precisely what you are looking for.
– Anurag A S
2 hours ago
Thank you I will take a look!
– Michael
2 hours ago
add a comment |Â
You might want to take a look at this link geeksforgeeks.org/counting-inversions It does precisely what you are looking for.
– Anurag A S
2 hours ago
Thank you I will take a look!
– Michael
2 hours ago
You might want to take a look at this link geeksforgeeks.org/counting-inversions It does precisely what you are looking for.
– Anurag A S
2 hours ago
You might want to take a look at this link geeksforgeeks.org/counting-inversions It does precisely what you are looking for.
– Anurag A S
2 hours ago
Thank you I will take a look!
– Michael
2 hours ago
Thank you I will take a look!
– Michael
2 hours ago
add a comment |Â
4 Answers
4
active
oldest
votes
up vote
3
down vote
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')]
answered 2 hours ago
jpp
77.2k184491
I think I found a way without using the indices at all.
– Mad Physicist
2 hours ago
Hello, I am not too familiar with "from itertools import combinations" could you explain how that function works? Currently, I am writing using nested for loops but cant quite get the results yet.
– Michael
1 hour ago
add a comment |Â
up vote
2
down vote
An efficient version of @jpp's solution is as follows:
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')]
Note that aPairs are combinations of (index, book) tuples and each combination is sorted by the index which guarantees that in each pair of books, the first is "better" than the next (for user A).
Now to compute ordering mismatches, we just need to decide whether the corresponding book indices in lstB also preserve this ordering.
Edit
As @MadPhysicist noted, combinations preserves the original order in the array in each generated tuple, so no need to create aPairs as a list of sorted (index, book) tuples. We can directly generate mismatches with just 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]]
answered 2 hours ago
slider
4,294927
I think my way may be even further cleaned up.
– Mad Physicist
2 hours ago
add a comment |Â
up vote
2
down vote
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.
answered 2 hours ago
Mad Physicist
31.5k156490
Nice! Although is it guaranteed that all orderings you generate withcombinations(lstA, 2)will be "positive orderings"?
– slider
1 hour ago
1
@slider. Yes, that's what the docs seem to be guaranteeing (docs.python.org/3/library/itertools.html#itertools.combinations), and this confirms: ideone.com/dExkt4
– Mad Physicist
1 hour ago
@slider: I've updated my answer
– Mad Physicist
1 hour ago
Great. Based on that, I think I can simplify mine too a little bit more.
– slider
1 hour ago
1
@slider: hope someone clears this up for us stackoverflow.com/q/53112861/2988730
– Mad Physicist
1 hour ago
 |Â
show 2 more comments
up vote
0
down vote
You can use iter and then compare indices
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')]
answered 1 hour ago
vash_the_stampede
3,7411319
This seems awfully inefficient compared to the other answers, but is probably easier to understand.
– Mad Physicist
1 hour ago
@MadPhysicist How would this be less efficient, other methods are creating extra wasted combinations then filtering through them, this only creates one list of only pairs that will be used
– vash_the_stampede
56 mins ago
You're doing a linear search for each element in both lists for one thing. For example, you could useenumeratein your outer loop to avoidlstA.index(i). Your algorithm probably does indeed save a fraction of the space, but at the cost of a dramatic increase in time.
– Mad Physicist
51 mins ago
@MadPhysicist hmm yeah I guess, Just this same type of problem was at hand before and I usedcombinations disgarding the unused and was made a point of by MartijnPeters about how inefficient it can be do create all sorts of combinations just to filter a few out
– vash_the_stampede
49 mins ago
add a comment |Â
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
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')]
answered 2 hours ago
jpp
77.2k184491
I think I found a way without using the indices at all.
– Mad Physicist
2 hours ago
Hello, I am not too familiar with "from itertools import combinations" could you explain how that function works? Currently, I am writing using nested for loops but cant quite get the results yet.
– Michael
1 hour ago
add a comment |Â
up vote
3
down vote
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')]
answered 2 hours ago
jpp
77.2k184491
I think I found a way without using the indices at all.
– Mad Physicist
2 hours ago
Hello, I am not too familiar with "from itertools import combinations" could you explain how that function works? Currently, I am writing using nested for loops but cant quite get the results yet.
– Michael
1 hour ago
add a comment |Â
up vote
3
down vote
up vote
3
down vote
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')]
answered 2 hours ago
jpp
77.2k184491
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')]
answered 2 hours ago
jpp
77.2k184491
answered 2 hours ago
jpp
77.2k184491
answered 2 hours ago
jpp
77.2k184491
answered 2 hours ago
jpp
77.2k184491
77.2k184491
I think I found a way without using the indices at all.
– Mad Physicist
2 hours ago
Hello, I am not too familiar with "from itertools import combinations" could you explain how that function works? Currently, I am writing using nested for loops but cant quite get the results yet.
– Michael
1 hour ago
add a comment |Â
I think I found a way without using the indices at all.
– Mad Physicist
2 hours ago
Hello, I am not too familiar with "from itertools import combinations" could you explain how that function works? Currently, I am writing using nested for loops but cant quite get the results yet.
– Michael
1 hour ago
I think I found a way without using the indices at all.
– Mad Physicist
2 hours ago
I think I found a way without using the indices at all.
– Mad Physicist
2 hours ago
Hello, I am not too familiar with "from itertools import combinations" could you explain how that function works? Currently, I am writing using nested for loops but cant quite get the results yet.
– Michael
1 hour ago
Hello, I am not too familiar with "from itertools import combinations" could you explain how that function works? Currently, I am writing using nested for loops but cant quite get the results yet.
– Michael
1 hour ago
add a comment |Â
up vote
2
down vote
An efficient version of @jpp's solution is as follows:
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')]
Note that aPairs are combinations of (index, book) tuples and each combination is sorted by the index which guarantees that in each pair of books, the first is "better" than the next (for user A).
Now to compute ordering mismatches, we just need to decide whether the corresponding book indices in lstB also preserve this ordering.
Edit
As @MadPhysicist noted, combinations preserves the original order in the array in each generated tuple, so no need to create aPairs as a list of sorted (index, book) tuples. We can directly generate mismatches with just 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]]
answered 2 hours ago
slider
4,294927
I think my way may be even further cleaned up.
– Mad Physicist
2 hours ago
add a comment |Â
up vote
2
down vote
An efficient version of @jpp's solution is as follows:
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')]
Note that aPairs are combinations of (index, book) tuples and each combination is sorted by the index which guarantees that in each pair of books, the first is "better" than the next (for user A).
Now to compute ordering mismatches, we just need to decide whether the corresponding book indices in lstB also preserve this ordering.
Edit
As @MadPhysicist noted, combinations preserves the original order in the array in each generated tuple, so no need to create aPairs as a list of sorted (index, book) tuples. We can directly generate mismatches with just 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]]
answered 2 hours ago
slider
4,294927
I think my way may be even further cleaned up.
– Mad Physicist
2 hours ago
add a comment |Â
up vote
2
down vote
up vote
2
down vote
An efficient version of @jpp's solution is as follows:
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')]
Note that aPairs are combinations of (index, book) tuples and each combination is sorted by the index which guarantees that in each pair of books, the first is "better" than the next (for user A).
Now to compute ordering mismatches, we just need to decide whether the corresponding book indices in lstB also preserve this ordering.
Edit
As @MadPhysicist noted, combinations preserves the original order in the array in each generated tuple, so no need to create aPairs as a list of sorted (index, book) tuples. We can directly generate mismatches with just 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]]
answered 2 hours ago
slider
4,294927
An efficient version of @jpp's solution is as follows:
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')]
Note that aPairs are combinations of (index, book) tuples and each combination is sorted by the index which guarantees that in each pair of books, the first is "better" than the next (for user A).
Now to compute ordering mismatches, we just need to decide whether the corresponding book indices in lstB also preserve this ordering.
Edit
As @MadPhysicist noted, combinations preserves the original order in the array in each generated tuple, so no need to create aPairs as a list of sorted (index, book) tuples. We can directly generate mismatches with just 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]]
answered 2 hours ago
slider
4,294927
edited 1 hour ago
answered 2 hours ago
slider
4,294927
answered 2 hours ago
slider
4,294927
answered 2 hours ago
slider
4,294927
4,294927
I think my way may be even further cleaned up.
– Mad Physicist
2 hours ago
add a comment |Â
I think my way may be even further cleaned up.
– Mad Physicist
2 hours ago
I think my way may be even further cleaned up.
– Mad Physicist
2 hours ago
I think my way may be even further cleaned up.
– Mad Physicist
2 hours ago
add a comment |Â
up vote
2
down vote
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.
answered 2 hours ago
Mad Physicist
31.5k156490
Nice! Although is it guaranteed that all orderings you generate withcombinations(lstA, 2)will be "positive orderings"?
– slider
1 hour ago
1
@slider. Yes, that's what the docs seem to be guaranteeing (docs.python.org/3/library/itertools.html#itertools.combinations), and this confirms: ideone.com/dExkt4
– Mad Physicist
1 hour ago
@slider: I've updated my answer
– Mad Physicist
1 hour ago
Great. Based on that, I think I can simplify mine too a little bit more.
– slider
1 hour ago
1
@slider: hope someone clears this up for us stackoverflow.com/q/53112861/2988730
– Mad Physicist
1 hour ago
 |Â
show 2 more comments
up vote
2
down vote
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.
answered 2 hours ago
Mad Physicist
31.5k156490
Nice! Although is it guaranteed that all orderings you generate withcombinations(lstA, 2)will be "positive orderings"?
– slider
1 hour ago
1
@slider. Yes, that's what the docs seem to be guaranteeing (docs.python.org/3/library/itertools.html#itertools.combinations), and this confirms: ideone.com/dExkt4
– Mad Physicist
1 hour ago
@slider: I've updated my answer
– Mad Physicist
1 hour ago
Great. Based on that, I think I can simplify mine too a little bit more.
– slider
1 hour ago
1
@slider: hope someone clears this up for us stackoverflow.com/q/53112861/2988730
– Mad Physicist
1 hour ago
 |Â
show 2 more comments
up vote
2
down vote
up vote
2
down vote
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.
answered 2 hours ago
Mad Physicist
31.5k156490
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.
answered 2 hours ago
Mad Physicist
31.5k156490
edited 1 hour ago
answered 2 hours ago
Mad Physicist
31.5k156490
answered 2 hours ago
Mad Physicist
31.5k156490
answered 2 hours ago
Mad Physicist
31.5k156490
31.5k156490
Nice! Although is it guaranteed that all orderings you generate withcombinations(lstA, 2)will be "positive orderings"?
– slider
1 hour ago
1
@slider. Yes, that's what the docs seem to be guaranteeing (docs.python.org/3/library/itertools.html#itertools.combinations), and this confirms: ideone.com/dExkt4
– Mad Physicist
1 hour ago
@slider: I've updated my answer
– Mad Physicist
1 hour ago
Great. Based on that, I think I can simplify mine too a little bit more.
– slider
1 hour ago
1
@slider: hope someone clears this up for us stackoverflow.com/q/53112861/2988730
– Mad Physicist
1 hour ago
 |Â
show 2 more comments
Nice! Although is it guaranteed that all orderings you generate withcombinations(lstA, 2)will be "positive orderings"?
– slider
1 hour ago
1
@slider. Yes, that's what the docs seem to be guaranteeing (docs.python.org/3/library/itertools.html#itertools.combinations), and this confirms: ideone.com/dExkt4
– Mad Physicist
1 hour ago
@slider: I've updated my answer
– Mad Physicist
1 hour ago
Great. Based on that, I think I can simplify mine too a little bit more.
– slider
1 hour ago
1
@slider: hope someone clears this up for us stackoverflow.com/q/53112861/2988730
– Mad Physicist
1 hour ago
Nice! Although is it guaranteed that all orderings you generate with
combinations(lstA, 2) will be "positive orderings"?– slider
1 hour ago
Nice! Although is it guaranteed that all orderings you generate with
combinations(lstA, 2) will be "positive orderings"?– slider
1 hour ago
1
1
@slider. Yes, that's what the docs seem to be guaranteeing (docs.python.org/3/library/itertools.html#itertools.combinations), and this confirms: ideone.com/dExkt4
– Mad Physicist
1 hour ago
@slider. Yes, that's what the docs seem to be guaranteeing (docs.python.org/3/library/itertools.html#itertools.combinations), and this confirms: ideone.com/dExkt4
– Mad Physicist
1 hour ago
@slider: I've updated my answer
– Mad Physicist
1 hour ago
@slider: I've updated my answer
– Mad Physicist
1 hour ago
Great. Based on that, I think I can simplify mine too a little bit more.
– slider
1 hour ago
Great. Based on that, I think I can simplify mine too a little bit more.
– slider
1 hour ago
1
1
@slider: hope someone clears this up for us stackoverflow.com/q/53112861/2988730
– Mad Physicist
1 hour ago
@slider: hope someone clears this up for us stackoverflow.com/q/53112861/2988730
– Mad Physicist
1 hour ago
 |Â
show 2 more comments
up vote
0
down vote
You can use iter and then compare indices
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')]
answered 1 hour ago
vash_the_stampede
3,7411319
This seems awfully inefficient compared to the other answers, but is probably easier to understand.
– Mad Physicist
1 hour ago
@MadPhysicist How would this be less efficient, other methods are creating extra wasted combinations then filtering through them, this only creates one list of only pairs that will be used
– vash_the_stampede
56 mins ago
You're doing a linear search for each element in both lists for one thing. For example, you could useenumeratein your outer loop to avoidlstA.index(i). Your algorithm probably does indeed save a fraction of the space, but at the cost of a dramatic increase in time.
– Mad Physicist
51 mins ago
@MadPhysicist hmm yeah I guess, Just this same type of problem was at hand before and I usedcombinations disgarding the unused and was made a point of by MartijnPeters about how inefficient it can be do create all sorts of combinations just to filter a few out
– vash_the_stampede
49 mins ago
add a comment |Â
up vote
0
down vote
You can use iter and then compare indices
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')]
answered 1 hour ago
vash_the_stampede
3,7411319
This seems awfully inefficient compared to the other answers, but is probably easier to understand.
– Mad Physicist
1 hour ago
@MadPhysicist How would this be less efficient, other methods are creating extra wasted combinations then filtering through them, this only creates one list of only pairs that will be used
– vash_the_stampede
56 mins ago
You're doing a linear search for each element in both lists for one thing. For example, you could useenumeratein your outer loop to avoidlstA.index(i). Your algorithm probably does indeed save a fraction of the space, but at the cost of a dramatic increase in time.
– Mad Physicist
51 mins ago
@MadPhysicist hmm yeah I guess, Just this same type of problem was at hand before and I usedcombinations disgarding the unused and was made a point of by MartijnPeters about how inefficient it can be do create all sorts of combinations just to filter a few out
– vash_the_stampede
49 mins ago
add a comment |Â
up vote
0
down vote
up vote
0
down vote
You can use iter and then compare indices
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')]
answered 1 hour ago
vash_the_stampede
3,7411319
You can use iter and then compare indices
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')]
answered 1 hour ago
vash_the_stampede
3,7411319
answered 1 hour ago
vash_the_stampede
3,7411319
answered 1 hour ago
vash_the_stampede
3,7411319
answered 1 hour ago
vash_the_stampede
3,7411319
3,7411319
This seems awfully inefficient compared to the other answers, but is probably easier to understand.
– Mad Physicist
1 hour ago
@MadPhysicist How would this be less efficient, other methods are creating extra wasted combinations then filtering through them, this only creates one list of only pairs that will be used
– vash_the_stampede
56 mins ago
You're doing a linear search for each element in both lists for one thing. For example, you could useenumeratein your outer loop to avoidlstA.index(i). Your algorithm probably does indeed save a fraction of the space, but at the cost of a dramatic increase in time.
– Mad Physicist
51 mins ago
@MadPhysicist hmm yeah I guess, Just this same type of problem was at hand before and I usedcombinations disgarding the unused and was made a point of by MartijnPeters about how inefficient it can be do create all sorts of combinations just to filter a few out
– vash_the_stampede
49 mins ago
add a comment |Â
This seems awfully inefficient compared to the other answers, but is probably easier to understand.
– Mad Physicist
1 hour ago
@MadPhysicist How would this be less efficient, other methods are creating extra wasted combinations then filtering through them, this only creates one list of only pairs that will be used
– vash_the_stampede
56 mins ago
You're doing a linear search for each element in both lists for one thing. For example, you could useenumeratein your outer loop to avoidlstA.index(i). Your algorithm probably does indeed save a fraction of the space, but at the cost of a dramatic increase in time.
– Mad Physicist
51 mins ago
@MadPhysicist hmm yeah I guess, Just this same type of problem was at hand before and I usedcombinations disgarding the unused and was made a point of by MartijnPeters about how inefficient it can be do create all sorts of combinations just to filter a few out
– vash_the_stampede
49 mins ago
This seems awfully inefficient compared to the other answers, but is probably easier to understand.
– Mad Physicist
1 hour ago
This seems awfully inefficient compared to the other answers, but is probably easier to understand.
– Mad Physicist
1 hour ago
@MadPhysicist How would this be less efficient, other methods are creating extra wasted combinations then filtering through them, this only creates one list of only pairs that will be used
– vash_the_stampede
56 mins ago
@MadPhysicist How would this be less efficient, other methods are creating extra wasted combinations then filtering through them, this only creates one list of only pairs that will be used
– vash_the_stampede
56 mins ago
You're doing a linear search for each element in both lists for one thing. For example, you could use
enumerate in your outer loop to avoid lstA.index(i). Your algorithm probably does indeed save a fraction of the space, but at the cost of a dramatic increase in time.– Mad Physicist
51 mins ago
You're doing a linear search for each element in both lists for one thing. For example, you could use
enumerate in your outer loop to avoid lstA.index(i). Your algorithm probably does indeed save a fraction of the space, but at the cost of a dramatic increase in time.– Mad Physicist
51 mins ago
@MadPhysicist hmm yeah I guess, Just this same type of problem was at hand before and I used
combinations disgarding the unused and was made a point of by MartijnPeters about how inefficient it can be do create all sorts of combinations just to filter a few out– vash_the_stampede
49 mins ago
@MadPhysicist hmm yeah I guess, Just this same type of problem was at hand before and I used
combinations disgarding the unused and was made a point of by MartijnPeters about how inefficient it can be do create all sorts of combinations just to filter a few out– vash_the_stampede
49 mins ago
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53112212%2flist-comparison-of-element%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
You might want to take a look at this link geeksforgeeks.org/counting-inversions It does precisely what you are looking for.
– Anurag A S
2 hours ago
Thank you I will take a look!
– Michael
2 hours ago