Checking all elements against each other for elements strictly worse

Question

Consider the following function:

def test_func(all_copies, checker):
    bad_copies = set(c[0] for c in itertools.permutations(all_copies, 2) if not checker(*c))
    all_copies = [c for c in all_copies if c not in bad_copies]
    return all_copies

This function returns a list of elements that are not overshadowed by any other element. Considering the checker:

def checker(l, r):
    return l[0] < r[1] or l[1] < r[1]

and the input:

all_copies = [(2,3)(2,2),(3,3),(3,1),(1,3),(4,1)]

This will return:

[(2,2),(3,1),(1,3)]

Now this works in 3 steps:

First itertools.permutations creates all combinations to check against. Secondly set() - because it can only contain one of each element is basically an "any". And any(not(x)) is basically the complement of all(x). So if an element turns "strictly worse" against any other element it is added to the "bad_copies". Finally the last line selects all elements that are not bad copies.

Now this seems nice, but it basically performs the check n² - n times. And the takes another O(n) to create the list.

Can I optimize this? Can the code become more clear and direct?

A more elaborate function that does the same thing is (can this be optimized using list comprehensions):

def test_func(all_copies):
    out = []
    for i in all_copies:
        add = True
        for j in all_copies:
            if i != j:
                if not check_post(i,j):
                    add = False
        if add:
            out.append(i)
    return out

Answer 1

Simplify

I do not know about performance but you are over-complicating your test_func function:

def test_func(all_copies):
    out = []
    for i in all_copies:
        add = True
        for j in all_copies:
            if i != j:
                if not check_post(i,j):
                    add = False
        if add:
            out.append(i)
    return out

You may use all

def test_func(all_copies):
    out = []
    for i in all_copies:
        if all(i == j or check_post(i,j) for j in all_copies)
            out.append(i)
    return out

And a generator saves both code and space over returning a list:

def test_func(all_copies):
    for i in all_copies:
        if all(i == j or check_post(i,j) for j in all_copies)
            yield i

Answer 2

Disclaimer: this is not a review but an extended comment.

You surely can optimize. The problem you are trying to solve is known as finding a non-dominated set, and allows a best case of \$O(n \log n)\$ solution; worst case is of course \$O(n^2)\$. You may want to start here.