如何在 Python 中递归比较 2 个列表(未排序，与顺序无关)

Question

我遇到的最后一个问题是能够准确地比较两个没有共同元素的相同大小的列表。我不能使用任何内置的 Python 函数(即排序、比较、计数器(，除了列表方法 len、del、index。

我的代码：

def SameStuff(l1, l2):
if len(l1) <= 1 or len(l2) <= 1 or len(l1) != len(l2):
if len(l1) == 0 or len(l2) == 0:   
return len(l1) == len(l2)
else:                    
return len(l1) == len(l2) and l1[0] == l2[0]     
else:
if l1[0] == l2[0]:                                          
return SameStuff(l1[1:], l2[1:])                 
else:
return SameStuff(l1, l2[1:]+[l2[0]]) 

Answer 1

你的解释令人困惑：

比较没有共同元素的相同大小的两个列表

您如何比较没有任何共同点的列表？ 您似乎想比较两个列表以查看它们是否包含相同的元素，但按任何顺序。 至于只用len()、del()和index()的函数/方法，我相信只需index()就可以做到：

def SameStuff(l1, l2):
if l1 and l2:  # both contain something
try:
index = l2.index(l1[0])
return SameStuff(l1[1:], l2[:index] + l2[1 + index:])  # recurse
except ValueError:
return False  # a value in one wasn't found in the other
return not(l1 or l2)  # only one contains something (False), or neither do (True)

这种解决方案也不会破坏其论点。

Answer 2

在不考虑顺序的情况下比较 2 个列表的最有效方法是使用collections.Counter，因为它需要的平均时间复杂度仅为 O(n(，但由于您不能使用它，您可以使用两个字典自行实现相同的主体来跟踪每个列表中每个不同项目的计数：

def compare(l1, l2, d1=None, d2=None):
if not d1:
d1, d2 = {}, {}
if l1 and l2:
d1[l1.pop()] = d1.get(l1[-1], 0) + 1
d2[l2.pop()] = d2.get(l2[-1], 0) + 1
return compare(l1, l2, d1, d2)
elif not l1 and not l2:
return d1 == d2
return False

因此：

print(compare([2, 3, 5, 3], [3, 5, 2, 3]))
print(compare([2, 3, 5, 2], [3, 5, 2, 3]))
print(compare([2, 3, 5, 2], [3, 5, 2]))

将输出：

True
False
False

请注意，任何对列表进行切片或使用list.index的方法总是效率低下的，因为需要 O(n( 来对列表中的每个项目执行这些操作，从而导致 O(n^2( 总体时间复杂度。

Answer 3

def SameStuff(l1, l2):
if l1 == []: return l2 == []
if len(l1) != len(l2): return False
else: return SameStuff(l1[1:], [x for x in l2 if x != l1[0]])

这是独立工作顺序。

以下版本还允许重复列表中的元素。

def SameStuff(l1, l2):
if l1 == []: return l2 == []    
elif len(l1) != len(l2): return False  
elif l1[0] in l2: 
i = l2.index(l1[0]) 
return SameStuff(l1[1:], l2[:i] + l2[i+1:]) 
else: return False