找到一对不相交的配对

Question

找到一对不相交的配对

3

假设有n个整数的配对集合，有没有一种快速的方法来确定是否存在两个配对(x₁, y₁)和(x₂, y₂)，使得集合{x₁, y₁} 和{x₂, x₂}的交集为空？

例如，{(0,1), (0,2), (2,1), (3,2)}的答案为{(0,1), (3,2)}。但是{(0,1), (0,2), (2,1)}没有这样的一对配对。

在Python中，您可以尝试以下所有配对。

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²)的时间。你能得到更接近线性时间的东西吗？

- marshall

1

这似乎是一个你应该在cs.SE上问的问题。 - Bakuriu

@Bakuriu 确实有重叠，但我确实需要代码，所以stackoverflow似乎也很合适。 - marshall

2个回答

2

在阅读本文之前，请先阅读templatetypedef的回答。

^{如果您只点赞本篇文章而不给他的回答点赞，我会亲自追踪您的。}

以下是一个Python实现，代码已经很清晰易懂了：templatetypedef的回答中有更详细的算法解释。

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为空，则结果始终为空，而空set的bool为False，这是正确的。

- Bakuriu

如果 seq = [[2,0], [3,0]]，则输出应为 False，但该代码给出的是 True。 - marshall

@marshall 我可能已经修复了它。那个输入的问题在于，当构建A组时，我们找不到任何匹配的对。因此，在最后，代码检查3是否在A组中，由于它是空的，所以是真的，并假设存在一对。但是只有在A组不为空的情况下才能这样说。 - Bakuriu

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

以下算法应该可以在O(n)时间内运行。它基于以下观察：如果你有一对{a，b}，那么每个其他的对都是：

1.不包括a或b，或者

2.至少包含一个a或b。

如果您选择任何一组{a，b}并将每个其他集合分类到这五个类别之一，请注意，如果您在情况1中得到任何内容，则完成并且您知道存在这样的一对。因此，唯一有趣的情况是当每个其他集合都属于第二种情况时。当发生这种情况时，我们可以将两个组称为“A”组和“B”组（匹配a的组和匹配b的组）。

一旦您有了A组和B组，您就知道没有两个A集可以成为您想要的一对，没有两个B集可以成为您想要的一对，并且集合{a，b}不能成为您想要的一对的一部分。只有一个选择，即如果您可以从A组中拿出某些东西并将其与B组中的某些东西配对。这仅在A组的某个非A组件与B组的任何非B组件均不匹配时发生。您可以通过构建一个哈希表来保存A组的非A组件，然后检查B组的每个元素是否在哈希集合中具有非B组件，以在O(n)时间内检查此问题。

总之，该算法是：

1.选择一对{a，b}。

2.对于每个其他的一对{c，d}：

-如果{a，b}和{c，d}不相交，则完成。

-否则，如果{a，b}={c，d}，则丢弃{c，d}。

-否则，如果它包含a，则将{c，d}放入A组；如果它包含b，则将其放入B组。

3.如果A组或B组为空，则不存在这样的一对。返回false。

4.对于A组的每个元素，添加一对的非a组件到哈希集合中。

5.如果B组的任何元素具有不在哈希集合中的非b组件，则返回true；否则返回false。

该算法的时间复杂度为O(n)，额外使用了O(n)的内存。

希望这可以帮助您！