How To Recursively Compare 2 Lists In Python (unsorted, Order-independent)

The last issue I have is being able to accurately compare two lists of the same size that have no elements in common. I cannot use any built in Python functions (i.e., sort, compar

Solution 1:

Your explanation is confusing:

compare two lists of the same size that have no elements in common

How do you compare lists that have nothing in common? It seems like you want to compare two lists to see if they contain the same elements, but in any order. As far as doing it only with the functions/methods len(), del(), and index(), I believe it can be done with just index():

defSameStuff(l1, l2):
    if l1 and l2:  # both contain somethingtry:
            index = l2.index(l1[0])

            return SameStuff(l1[1:], l2[:index] + l2[1 + index:])  # recurseexcept ValueError:

            returnFalse# a value in one wasn't found in the otherreturnnot(l1 or l2)  # only one contains something (False), or neither do (True)

This solution is also not destructive to its arguments.

Solution 2:

The most efficient way to compare 2 lists with no regard to order is with collections.Counter as it takes an average time complexity of just O(n), but since you can't use it, you can instead implement the same principal on your own using two dicts to keep track of the counts of each distinct item in each list:

defcompare(l1, l2, d1=None, d2=None):
    ifnot d1:
        d1, d2 = {}, {}
    if l1 and l2:
        d1[l1.pop()] = d1.get(l1[-1], 0) + 1
        d2[l2.pop()] = d2.get(l2[-1], 0) + 1return compare(l1, l2, d1, d2)
    elifnot l1 andnot l2:
        return d1 == d2
    returnFalse

so that:

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

would output:

TrueFalseFalse

Note that any approach that slices a list or uses list.index is always going to be inefficient because it takes O(n) to do each of those for every item in the lists, resulting in O(n^2) overall time complexity.

Solution 3:

defSameStuff(l1, l2):
        if l1 == []: return l2 == []
        iflen(l1) != len(l2): returnFalseelse: return SameStuff(l1[1:], [x for x in l2 if x != l1[0]])

This works order independently.

And the following version allows also repetitions of elements in the lists.

defSameStuff(l1, l2):
    if l1 == []: return l2 == []    
    eliflen(l1) != len(l2): returnFalseelif l1[0] in l2: 
        i = l2.index(l1[0]) 
        return SameStuff(l1[1:], l2[:i] + l2[i+1:]) 
    else: returnFalse