Compare objects from more than 2 lists

Question

Is there a way to compare all 2-item combinations of more than 2 lists?

Let's say there is an object:

class obj():
   def __init__():
       self.name = # some name
       self.number = random(10)
   def equals(obj):
       if self.number == obj.number:
           return True
       else: return False

list1,list2,list3....listX - all these lists contain instances of class obj

I want to compare all 2-item combinations from these lists and return equal objects.

So if there is an obj in list2 which obj.number attribute is 5 and obj in list8 which has obj.number 5, it will be returned.

For two lists the comparison would be simple:

   for obj1 in list1:
      for obj2 in list2:
          if obj1.equals(obj2):
               print obj1,obj2

But I don't know how to make this comparison for more lists of objects. Do you have any advice?

Answer 1

As you might know, with X lists, the time complexity will go up to O(n^X), which is far from optimal (in the case that all lists have the same length =n)

Now it all depends on what you actually want as output. It seems to me that you want to find objects that are present in multiple lists.

One way to do this in a more performant way is to use a dictionary (hashmap) and iterate trough every list. Hash objects based on their self.number.

This will result in something like: {1: [obj1], 2: [obj2, obj3], 3: [obj4], ...}, where the keys are the numbers of the objects and the values are the objects that have these values as number.

By running over this dictionary and only considering entries that have a list with a size larger or equal than 2, you will end up with the objects that are equal.

here the time complexity is equal to the O(n*X), which is ~ O(n)

---

To illustrate this, I've created a short simple example that uses 2 lists:

from collections import defaultdict

class Obj():
   def __init__(self, value):
       self.number = value


def find_equals(list1,list2):
    d = defaultdict(list)
    for obj1 in list1:
        d[obj1.number].append(obj1)
    for obj2 in list2:
        d[obj2.number].append(obj2)
    return [d[i] for i in d if len(d[i]) >= 2]

def test():
    l1 = [Obj(1),Obj(2),Obj(3),Obj(4)]
    l2 = [Obj(5),Obj(2),Obj(3),Obj(6)]
    print find_equals(l1,l2)
test()

It can probably be optimised with nifty python constructs, but it shows the idea behind it.

The output is:

[[<__main__.Obj instance at 0x103278440>, <__main__.Obj instance at 0x103278560>], [<__main__.Obj instance at 0x103278488>, <__main__.Obj instance at 0x1032785a8>]]

Which are the objects with the numbers 2 and 3, that were used in the test sample.