How do I recursively compare lists-CodePudding

I have to recursively write ( without loops) the compare_the_lists function which gets two two-dimensional lists of numbers (each of which is represented by a list of number lists).

The function will return True if the two two-dimensional lists are identical in all their values, and False if there is at least one element in which they differ.

The external list, as well as the internal lists, can be empty, and the length of the internal lists in each of the two-dimensional lists may not be the same.

Also, if the length of the external lists list1 and list2 is different, or alternatively, the length of internal lists located in the same position in the external lists list1 and list2 is different, False must also be returned. Example: Input:

list1=[[1,2],[4,5,8]]

list2=[[1,2],[4,5,6]]

Output:

False (because 6!= 8).

Notes:

The == operator may not be used over lists (one-dimensional or two-dimensional), but the == operator may be used to compare numbers.
And slicing is also not allowed (I can use Pop and any other action as long as I do not change the input).

Here is the code I wrote down so far, the problem is that after I wrote it down I noticed that slicing and ‘==‘ on lists are not allowed.

def compare_the_lists(list1,list2):
    len_1 = len(list1)
    len_2 = len(list2)

    if len_1 == 0:
        return len_2 == 0
    if len_1 != len_2:
        return False
    if list1[0] != list2[0]:
        return False
  
    return compare_the_lists(list1[:], list2[1:])

I would be happy for any help in changing the problematic things.(the slicing and the ‘==‘).

CodePudding user response：

If you aren't allowed to use the [] operator (it's not clear whether the [0] in your existing code counts as a "slice" for your purposes, but your question says it's "problematic" so I assume it does), but you are allowed to pop and append, and you aren't allowed to mutate the input, I think the best approach is to pop() before you recurse and then append before you return:

def compare_the_lists(list1, list2):
    if not isinstance(list1, list) and not isinstance(list2, list):
        return list1 == list2
    if not isinstance(list1, list) or not isinstance(list2, list):
        return False

    if len(list1) == 0 and len(list2) == 0:
        return True
    if len(list1) == 0 or len(list2) == 0:
        return False

    i = list1.pop()
    j = list2.pop()
    equal = compare_the_lists(i, j) and compare_the_lists(list1, list2)
    list1.append(i)
    list2.append(j)
    return equal

That way the popped elements are stored on the call stack and get restored in their original order:

>>> list1=[[1,2],[4,5,8]]
>>> list2=[[1,2],[4,5,6]]
>>> compare_the_lists(list1, list2)
False
>>> list1, list2
([[1, 2], [4, 5, 8]], [[1, 2], [4, 5, 6]])

CodePudding user response：

I've tried to write this as a recursive function which will work on any depth of nested dicts (rather than just two):

def recursive_list_compare(a, b):
    # This is our base case, we have two ints. Are they the same?
    if isinstance(a, int) and isinstance(b, int):
        return a == b

    # These are early returns. We expect two lists of the same size
    if not isinstance(a, list) or not isinstance(b, list) or len(a) != len(b):
        return False

    # Get pairwise elements from both lists
    for sub_a, sub_b in zip(a, b):
        # Bail out quickly if any sub-element is not equal
        if not recursive_list_compare(sub_a, sub_b):
            return False

    # Looks like we are all good!
    return True

For example, it should spot the difference in the nested dict at the end there.

list_1 = [[1, 2], [4, 5, 8, [12]]]
list_2 = [[1, 2], [4, 5, 8, [12, 1]]]
print(recursive_list_compare(list_1, list_2))  # False!
print(recursive_list_compare(list_1, list_1))  # True!