Как рекурсивно сравнить 2 списка в Python (несортированные, независимые от порядка)

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