logo标签列表

元素列表比较

pythonlistsorting
6

我有一个问题，对我来说有点难以解释，因此我会用很多例子来帮助大家理解并看看能否帮助我。

假设我有两个列表，它们包含由两个人从最好到最差评价的书名。用户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')也可以]

用户一还评价“五十度灰”比“德古拉”更好，用户二也评价“五十度灰”比“德古拉”更好（分别是索引2、3和0、1）。在这种情况下，什么也不会发生。

程序的最终结果应该返回一个元组列表，因此，

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

有人能帮我指出正确的方向，提供一个可以得到所有元组的算法吗？

你可能想看一下这个链接 https://www.geeksforgeeks.org/counting-inversions/ 它恰好做了你要找的事情。 - Anurag A S
看起来你有不选择答案的习惯。每当你选择一个答案时，你将会获得一些声望，并且你的问题也会为未来的读者提供一个标准答案。请在它们对你有帮助时选择答案。 - Mad Physicist
4个回答
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')]
我认为我找到了一种方法，完全不使用索引。 - Mad Physicist
你好，我对“from itertools import combinations”不太熟悉，你能解释一下这个函数是如何工作的吗？目前我正在使用嵌套的for循环编写代码，但还不能得到想要的结果。 - Michael
3

一个方法是将每个列表中的所有正序序列累积到一个集合中，然后取两个集合之间的差异。正序序列是指当 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方法而不是-运算符，因为这样就不需要从生成器表达式中创建一个集合对象。不幸的是，你不能仅仅使用symmetric_difference/^，因为元素是被反转的。第三步只是计算结果的并集。

IDEOne链接：https://ideone.com/DuHTed。这演示了原始问题和非对称列表的情况。

不错！但是你使用combinations(lstA, 2)生成的所有排序都保证是“正序”吗？ - slider
1
@slider。是的，文档似乎保证了这一点（https://docs.python.org/3/library/itertools.html#itertools.combinations），并且这个链接也证实了这一点：https://ideone.com/dExkt4 - Mad Physicist
太好了。基于此，我认为我也可以进一步简化我的代码。 - slider
我仍然不理解“组合按词典顺序排列。因此，如果输入的可迭代对象已排序，则组合元组将按排序顺序生成。”显然，这里的列表没有按“词典顺序”排序，从我所理解的意思来看，这意味着按字母顺序排列。 - slider
@滑块。我认为关键在于下一段：元素是根据它们的位置而不是它们的值被视为唯一的。从这个意义上讲，当你只考虑索引时，它是按字典顺序排序的。我不太确定，所以我马上会问一个问题。 - Mad Physicist
1
@slider：希望有人能为我们澄清这个问题 https://dev59.com/L1QJ5IYBdhLWcg3wx4-p - Mad Physicist
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) 元组列表。我们可以直接使用 bIndices 生成 mismatches：
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]]
我认为我的方法可能需要进一步优化。 - Mad Physicist
0
你可以使用 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')]
与其他答案相比，这似乎非常低效，但可能更容易理解。 - Mad Physicist
@MadPhysicist 这种方法为什么会更高效呢？其他方法会创建额外的无用组合，然后再通过筛选来处理，而这种方法只会创建一个仅包含将被使用的配对的列表。 - vash_the_stampede
你正在为每个列表中的元素执行线性搜索。例如，你可以在外部循环中使用enumerate来避免使用lstA.index(i)。你的算法可能确实节省了一小部分空间，但代价是时间的大幅增加。 - Mad Physicist
@MadPhysicist 嗯，我想是的。之前也遇到过同样类型的问题，我使用了“组合”来丢弃未使用的内容，并被MartijnPeters指出这种方法的低效性，因为创建各种组合只是为了过滤掉其中的一些。 - vash_the_stampede
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接