找到一对双无交集 [英] Find a pair of pairs with no intersection

问题描述

给定一组n对整数的，是有一个快速的方法，以确定是否存在2对（X <分> 1 ，Y <子> 1 ）和（x <子> 2 ，Y ₂ ），从而使集合的交集{X <子> 1 ，Y <子> 1 }和{X <子> 2 ，X ₂ }是空的？

Given a set of n pairs of integers, is there a fast way to determine if there exists two pairs (x₁, y₁) and (x₂, y₂) so that the intersection of the sets {x₁, y₁} and {x₂, x₂} is empty?

例如，{（0,1），（0,2），（2,1），（3,2）}的{（0,1），（3,2）}作为一个答案。然而{（0,1），（0,2），（2,1）}没有这样的一对对的

For example, {(0,1), (0,2), (2,1), (3,2)} has {(0,1), (3,2)} as an answer. However {(0,1), (0,2), (2,1)} has no such pair of pairs.

在Python中，你可以只尝试所有对如下：

In Python, you could just try all pairs as follows.

l = [(0,1), (0,2), (2,1), (3,2)]
print  [pairs for pairs in itertools.combinations(l, 2)
    if not (set(pairs[0]) & set(pairs[1]))]

此方法需要O（N ² ）的时间。你能得到的东西更接近线性的时间？

This approach takes O(n²) time. Can you get something closer to linear time?

推荐答案

^{我会亲自追捕谁upvotes这个答案没有upvoting他的答案，因为他的完成了所有的工作}

Before reading this read templatetypedef answer.

^{I'll personally hunt whoever upvotes this answer without upvoting his answer, since he did all the work}

下面是一个（不言自明）Python实现在定义的算法templatetypedef回答：

Here's a (self-explanatory) python implementation of the algorithm defined in templatetypedef answer:

def exists_pair(seq):
    if len(seq) < 2:
        return False
    a, b = seq[0]  # could be: seq.pop() if modifications are allowed
    a_group = set()
    b_group = set()
    for c, d in seq:
        if not ({a,b} & {c,d}):
            return True
        elif {a,b} == {c,d}:
            continue
        elif a in {c,d}:
            a_group.add(c if c != a else d)
        else:
            b_group.add(c if c != b else d)

    if not a_group:
        return False

    # b_group - a_group: elements of b_group that do not appear in a_group
    return bool(b_group - a_group)

有没有需要检查一个空的 b_group ，因为 b_group结果 - a_group 始终的一个子集 b_group 。如果 b_group 是空的，结果永远是空的，布尔空设置是假，这是正确的。

There's no need to check for an empty b_group because the result of b_group - a_group is always a subset of b_group. If b_group is empty the result will always be empty and bool of empty set is False, which is correct.

这篇关于找到一对双无交集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！