Проверьте, равны ли элементы и длина двух несортированных списков с помощью рекурсии

Question

Я пытаюсь написать чисто рекурсивную функцию, которая будет возвращать True, если два несортированных списка имеют одинаковую длину и содержат одинаковые элементы.Мне не разрешено использовать любую итерацию, только рекурсию.Вот пример того, что он должен делать:

>>> SameStuff(['Hello',1,2,3],[3,2,1,'Hello'])
True
>>> SameStuff(['HELLO',1,2,3],[3,'two',1,'Hello'])
False
>>> SameStuff([1,2],[])
False

Я борюсь с логикой моей рекурсивной функции, и мне не хватает некоторых элементов.Вот что у меня есть:

def SameStuff(list1,list2):
    if len(list1)!=len(list2):
        return False
    if #some base case:
        #return True?
    if list1[0] in list2:
        return SameStuff(list1[1:],list2)
    else:
        return False

Answer 1

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

Другая идея состоит в том, чтобы вставить еще три параметра по умолчанию (они не нужны для первого вызова функции): пустой словарь, целочисленный индекс и логическое значение.

Используйте логическое значение, чтобы указать, какой списокмы пересекаем индекс и указываем на текущий элемент списка (мы могли бы просто использовать знак индекса вместо логического).При обходе первого списка запишите в словаре счетчик каждого найденного уникального элемента, используя элемент в качестве ключа.В конце переверните логическое значение и просмотрите второй список, на этот раз вычитая из количества элементов в словаре.Удалите все элементы, достигшие нуля.Предполагая, что мы уже проверили соответствие длины списков, если элемент не найден в словаре, списки не совпадают.

Answer 3

Чтобы не делал петли, вы можете добавить параметр на вход вашей функции:

def SameStuff(list1,list2,i):
    if list1==[] and list2==[]:
        return True

    elif i>=len(list1):
        return False

    elif len(list1)!=len(list2):
        return False

    elif list1[i]==list2[0]:
        del list1[i]
        del list2[0]
        return SameStuff(list1,list2,0)
    else:
        return SameStuff(list1,list2,i+1)


print(SameStuff(["hello",1,4],[1,3,"hello"],0))
print(SameStuff(["hello",1,3],[1,3,"hello"],0))

Answer 4

Важно отметить, что отсутствующий базовый случай в вашем коде является тестом, если оба списка пусты.

Другим важным фактором является избегание удаления найденного элемента из любого из обоих полученных списков, посколькукоторые могут изменить их после вызова.

Это тот же код, что и ваш, с наименьшим количеством возможных модификаций, на мой взгляд:

def SameStuff(list1,list2):                                                   
    if len(list1)!=len(list2):
        return False
    if len(list1) == 0 and len(list2) == 0:
        return True
    if list1[0] in list2:
        list2b = list2[:]
        list2b.remove(list1[0])
        return SameStuff(list1[1:], list2b)
    else:
        return False


print(SameStuff(['Hello',1,2,3], [3,2,1,'Hello']))
print(SameStuff(['HELLO',1,2,3],[3,'two',1,'Hello']))
print(SameStuff([1,2],[]))

Answer 5

def SameStuff(list1, list2):

    # if both empty, they are equal
    if not list1 and not list2:
        return True

    # if unequal lengths, they are not equal
    if len(list1) != len(list2):
        return False

    # grab the first item from list1
    item = list1[0]

    # if it isn't in list2, they are not equal
    if item not in list2:
        return False

    # make copies so we don't disturb the original lists
    newlist1 = list1[:]
    newlist2 = list2[:]

    # remove the item from both copies
    newlist1.remove(item)
    newlist2.remove(item)

    # call ourself with the list copies
    return SameStuff(newlist1, newlist2)

Answer 6

def SameStuff(l1, l2):
    if l1 == []: return l2 == []    # if recursed down to empty lists -> True
    elif len(l1) != len(l2): return False   # if any length differences -> False
    elif l1[0] in l2: 
        i = l2.index(l1[0]) # identify index of first in l2 identical to l1[0]
        return SameStuff(l1[1:], l2[:i] + l2[i+1:]) # l2 without this element!
    else: return False

Работает независимо от заказа.А также, если несколько элементов встречаются несколько раз.

Answer 7

Я думаю, у вас большая часть логики в правильном месте.Вы просто пропускаете случай, когда оба будут пустыми, к тому времени, по-видимому, они были одинаковыми списками в разных (потенциально) порядках!

Вероятно, неэффективно с функцией удаления, но сложно вынуть одни и те же элементы из двухразные неупорядоченные списки.

def SameStuff(l1, l2):
    if not l1 and not l2:
        return True

    if len(l1) != len(l2):
        return False

    last_element = l1[-1]
    if last_element not in l2:
        return False

    l1.remove(last_element)
    l2.remove(last_element)

    return SameStuff(l1, l2)