How to do an n^2 search using any in python

user_5119871 0
Viewed 66

How can I search whether there is an a in a list X such that there is a b later in the same list X such that the predicate p(a,b) returns explicitly true?

I.e. since p is a commutative function and potentially compute-intensive, if I have already called p(a,b), then I wish to avoid calling p(b,a).

python
4 Answers

itertools.combinations() produces a sequence of tuples without repeating:

any(p(a,b) for a,b in itertools.combinations(values, 2))
user_7708300

You can often define a custom class with a __lt__ comparator to make an orderable type or a custom __hash__ method to make them hashable (must also define __eq__)

When creating your objects, make them instances of your custom type instead of whatever they normally are

class OrderableCustomType(WhateverBaseType):

    def __lt__(self, other):
        return self.some_property < other.some_property

class HashableCustomType(WhateverBaseType):

    def __eq__(self, other):
        return self.some_property == other.some_property

    def __hash__(self):
        return hash(self.some_property)

You can use this to combine several properties into one comparison (for example both height and weight) and take the opportunity to cache expensive comparison calculations (for example if a network request is required)

user_45410450

I finally stumbled upon a solution. I am supposing that python lists have constant time access into lists.

any(p(X[a],X[b]) for a in range(len(X)) for b in range(a,len(X)))
user_51198710

If you only want any() value in a collection of calculations, you can use next() to only calculate up to the first Truthy value

If the types are not hashable (though if you can arrange for them to be, your life will be easier!), you can keep the references in a list

Adapting your Answer

try:
    value = next(a for a in range(len(X)) for b in range(a,len(X)) if p(X[a],X[b]))
except StopIteration:
    value = False
user_45410450
Related