Travis Herbert Travis Herbert - 1 year ago 41
Python Question

how to make a function which tells if two lists are equivalent in python

This question will be really annoying due to the fact it is for a class and we have a lot of restrictions on our code.

The objective is to make a function to see if two lists (random ordered) have the same elements in them. So, if

would be
. Now the restrictions are that we cannot use any built-in functions except
. So I can't use anything like
or the like. I also am not allowed to edit the lists, so I could not check to see if items are in both lists then delete them as I go if they are in both lists until it is empty.

With all these restrictions, I'm running out of ideas. Please help.

Answer Source

Is recursivity allowed ? That way, you don't have to modify existing lists in place. Obviously, not very efficient, but given your requirements this shouldn't really be an issue here...

def are_items_equal(a, b):
    # First the guard clause: if the first list is empty,
    # return True if the second list is empty too, False otherwise
    if not a:
        return not b

    # There is now at least 1 item in list a
    # Perform a linear search in the b list to find a[0]
    # (could have used a "for" loop, but I assumed here this was
    # forbidden too)
    ib = 0;
    while ib < len(b):
        if a[0] == b[ib]:
            # At this point, we know that at index `ib` in list `b`
            # there is the same item as in `a[0]`
            # Both list match if the "rest" of those two lists match too
            # Check that by performing a recursive call to are_items_equal
            # (discarding the pair matched at this step)
            return are_items_equal(a[1:], b[:ib]+b[ib+1:])
        ib += 1

    # You only reach this point when `a[0]` was not found
    # in the `b` list.
    return False


test_case = (
    ([2,5,4], [4,2,5]),
    ([2, 2, 5, 4], [4, 5, 2, 5]),
    ([2,2,5,4], [4,2,5]),

for a,b in test_case:
    print(are_items_equal(a, b), a, b)


True [2, 5, 4] [4, 2, 5]
False [2, 2, 5, 4] [4, 5, 2, 5]
False [2, 2, 5, 4] [4, 2, 5]
True [2, 2, 5, 4] [4, 2, 5, 2]