CODEWITHSUNDEEP
pythonpython-3.xlistrecursion
peter58
peter58

Reputation: 39

Check if the elements and length of two unsorted lists are equal using recursion

I am trying to write a purely recursive function that will return True if two unsorted lists are of the same length and contain the same elements. I am not allowed to use any iteration, only recursion. Here is an example of what it should do:

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

I am struggling with the logic of my recursive function, and am missing some elements. Here's what I have:

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

Upvotes: 3

Views: 1722

Answers (7)

גלעד ברקן
גלעד ברקן

Reputation: 23945

Another idea is to insert three more default parameters (those would not be needed for the first function call): an empty dictionary, an integer index, and a boolean.

Use the boolean to indicate which list we are traversing and the index to point to the current list element (we could also just use a sign on the index instead of the boolean). When traversing the first list, record in the dictionary the count of each unique element encountered, using the element as key. At the end, flip the boolean and traverse the second list, this time subtracting from the counts of elements in the dictionary. Remove any elements reaching zero counts. Assuming we've already tested for matching list lengths, if an element is not found in the dictionary, the lists do not match.

Upvotes: 0

cdlane
cdlane

Reputation: 41905

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)

Upvotes: 0

Gwang-Jin Kim
Gwang-Jin Kim

Reputation: 9930

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

This works independent from order. And also if there are multiple occurrences of some elements.

Upvotes: 0

dallonsi
dallonsi

Reputation: 1526

In order to not make any loop, you can add a parameter in the input of your function:

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))

Upvotes: 0

Nicolás Ozimica
Nicolás Ozimica

Reputation: 9748

It is important to state that the missing base case in your code is test if both lists are empty.

The other important factor, is avoid to remove the found element from any of both received list, since that could alter them after the call.

This is the same code than yours, with the least modifications possible in my opinion:

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],[]))

Upvotes: 0

John Gordon
John Gordon

Reputation: 33335

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)

Upvotes: 1

LeKhan9
LeKhan9

Reputation: 1350

I think you have most of the logic in the right place. You are just missing the case when both will be empty, by then presumably they were the same lists in different (potentially) orders!

Probably not efficient with the remove function, but tricky to pop the same elements from two different unordered lists.

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)

Upvotes: 3

Related Questions