Checking all elements against each other for elements strictly worse

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 n2 - 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:
for j in all_copies:
if i != j:
if not check_post(i,j):
out.append(i)
return out

• What can we assume of the function checker? From the example we see it is not transitive, not reflexive, nothing. So I don't think anything better than O(n**2) is possible. Commented Jan 23, 2016 at 14:55
• Also, using your definition of test_func, checker, and all_copies, I get the empty list. Maybe add some more test-cases? Commented Jan 23, 2016 at 14:58

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:
for j in all_copies:
if i != j:
if not check_post(i,j):
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

• @MathiasEttinger I think nested ifs should become and Commented Jan 24, 2016 at 11:31
• @MathiasEttinger Your previous comment stated another condition... also my code is (not a) and (not b) different from not (a and b). Anyhow thanks for helping my out in this confusing boolean conditions. Commented Jan 24, 2016 at 11:39
• @MathiasEttinger thanks for testing it, from mobile I couldnt. imaginary +1 to you :) Commented Jan 24, 2016 at 12:12

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.