Найти пару пар, без пересечения

Question

Учитывая набор из п пар целых чисел, есть быстрый способ, чтобы определить, существует две пары (х , у) и (х , у) так, что пересечение множеств {х , у } и {х , х } пусто?

Например, {(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 2 ) времени. Можете ли вы получить что-то ближе к линейному времени?

Answer 1

Перед началом работы templatetypedef answer.

^{Я лично поохотиться кто upvotes этого ответа не upvoting своего ответа, так как он сделал всю работа}

---

Вот (сама за себя) реализация питон алгоритма определяется в 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 пусто, результат будет всегда пустым, а bool пустого set - False, что верно.

Answer 2

Следующий алгоритм должен работать в O (n) времени. Он основан на следующем наблюдении: если у вас есть пара {а, Ь}, то любая другая пара

1. не включает в себя или б, или
2. содержит по меньшей мере один из или б.

Если вы выберете любой набор {a, b} и классифицируете друг друга в одной из этих пяти категорий, обратите внимание, что если вы получите что-либо в случае 1, то вы закончите, и вы знаете, что такая пара существует , Итак, единственный интересный случай - когда каждый другой набор попадает в случай 2. Когда это произойдет, мы можем назвать две группы группой «A» и группой «B» (для множеств, которые соответствуют a и для множеств, соответствующих b).

Как только у вас есть группа A и группа B, вы знаете, что ни одна из двух наборов A не может быть той парой, которую вы хотите, никакие два набора B не могут быть вашей парой, а набор {a, b} t быть частью пары, которую вы хотите. Единственный вариант - если вы можете взять что-то из группы A и соединить его с чем-то из группы B. Это происходит только в том случае, если какой-либо не-компонент A из группы A не соответствует компоненту, отличному от B, из группы B. Вы можете проверить это в O (n), построив хэш-таблицу, содержащую не-A-компоненты группы A, а затем проверите для каждого элемента группы B, находится ли ее компонент, отличный от B, в хэш-наборе.

Подводя итог, алгоритм

• Выберите пару {а, Ь}.
• Для каждой другой пары {c, d}:
  • Если {a, b} и {c, d} не пересекаются, все готово.
  • В противном случае, если {a, b} = {c, d}, отбросьте {c, d}.
  • В противном случае поместите {c, d} в группу A, если она включает a или группу B, если она включает b.
• Если группа A или группа B пуста, пары не существует. Вернуть false.
• Для каждого элемента группы A добавьте не-компонент из пары в хэш-набор.
• Возвращает true, если какой-либо элемент группы B имеет не-b компонент не в хэш-наборе, а false в противном случае.

Это работает во времени O (n) и использует дополнительную память O (n).

Надеюсь, это поможет!