python - 如何制作一个函数来判断两个列表在python中是否等价

Question

这个问题真的很烦人，因为它是针对一个类的，而且我们对代码有很多限制。

目标是创建一个函数来查看两个列表（随机排序）是否具有相同的元素。所以，如果a=[2,5,4]和b=[4,2,5] a==b将是true。现在的限制是我们不能使用任何内置函数，除了len(). 所以我不能使用任何类似set()的东西。我也不允许编辑列表，所以我无法检查项目是否在两个列表中，然后删除它们，如果它们在两个列表中，直到它为空。

有了所有这些限制，我的想法已经不多了。请帮忙。

Answer 1

允许递归吗？这样，您不必就地修改现有列表。显然，效率不高，但考虑到您的要求，这应该不是问题......

def are_items_equal(a, b):
    # First the guard clause: if the first list is empty,
    # return True if the second list is empty too, False otherwise
    if not a:
        return not b

    # There is now at least 1 item in list a
    # Perform a linear search in the b list to find a[0]
    # (could have used a "for" loop, but I assumed here this was
    # forbidden too)
    ib = 0;
    while ib < len(b):
        if a[0] == b[ib]:
            # At this point, we know that at index `ib` in list `b`
            # there is the same item as in `a[0]`
            # Both list match if the "rest" of those two lists match too
            # Check that by performing a recursive call to are_items_equal
            # (discarding the pair matched at this step)
            return are_items_equal(a[1:], b[:ib]+b[ib+1:])
        ib += 1

    # You only reach this point when `a[0]` was not found
    # in the `b` list.
    return False

测试：

test_case = (
    ([2,5,4], [4,2,5]),
    ([2, 2, 5, 4], [4, 5, 2, 5]),
    ([2,2,5,4], [4,2,5]),
    ([2,2,5,4],[4,2,5,2]),
)

for a,b in test_case:
    print(are_items_equal(a, b), a, b)

生产：

True [2, 5, 4] [4, 2, 5]
False [2, 2, 5, 4] [4, 5, 2, 5]
False [2, 2, 5, 4] [4, 2, 5]
True [2, 2, 5, 4] [4, 2, 5, 2]

Answer 2

显然最好的解决方案是使用set()，但你受到限制。这是一种没有任何“内置功能”的方法：

def equal_lists(l1, l2):
    for i in l1:
        if not i in l2:
            return False
    for i in l2:
        if not i in l1:
            return False
    return True

编辑 如果你想“考虑两个列表的所有相同元素但每个列表的数量不同”：

def occur(it):
    d = {}
    for i in it:
        try:
            d[i] += 1
        except KeyError:
            d[i] = 1
    return d

occur(a) == occur(b)