Слияние задает итеративно, если они содержат более 50% элементов

Question

У меня есть функция, которая задает два набора A и B, возвращает маржированный набор A.union (B), если один из двух наборов разделяет не менее 50% его элементы с другим набором, ложных иначе:

def merged_set_or_false(set1, set2): 
    if **magic**: 
    return merged_set 
    else: 
    return False 

Теперь, что я хотел бы сделать, это перебирать список набора, пока не два набора в списке не может быть объединен больше. Каков эффективный способ сделать это? На мой взгляд, это выглядит как сокращение(), но без фактического сокращения обязательно до одного элемента.

Пример:

>>> list_of_sets = [(1,2,3,4),(2,3,4,5),(6,7,8,9)] 
>>> len(list_of_sets) 
3 
>>> new_list = merge_until_possible(list_of_sets) 
>>> new_list 
[(1,2,3,4,5),(6,7,8,9)] 
>>> len(new_list) 
2 

Идеи?

Edit - 4 декабря 2016 Только в случае, если кто-то может оказаться полезным, это мое текущее решение работы в прогресс для решения этой проблемы:

def pseudo_reduce(f, list_to_reduce): 
    """Perform f on two elements of list per time until possible.""" 
    reducing_is_still_possible = True 
    exit_loops = False 

    while reducing_is_still_possible: 
    initial_list_len = len(list_to_reduce) 
    for j in range(len(list_to_reduce)): 
     # If two elements became one in previous iter, we need to break twice 
     if exit_loops: 
     exit_loops = False 
     break 
     # If j is the last element, break to avoid out of index error 
     if j == (len(list_to_reduce) - 1): 
     break 
     for k in range(j + 1, len(list_to_reduce)): 
     element_or_false = f(list_to_reduce[j],list_to_reduce[k]) 
     if element_or_false: 
      # We remove the merged elements and append the new one 
      del list_to_reduce[k] 
      del list_to_reduce[j] 
      list_to_reduce.append(element_or_false) 
      exit_loops = True 
      break 

    if len(list_to_reduce) == initial_list_len: 
     reducing_is_still_possible = False 

return list_to_reduce 

Answer 1

Я думаю, что это не возможно напишите его как сокращение, потому что оператор (операция сокращения, которая должна быть функцией из двух списков множеств в список множеств) не ассоциативна: «сливающиеся» множества могут быть разделены совершенно другим набором. Если вы заказали свои входы (т. Е. Наборы с наиболее распространенными элементами всегда смежны), я думаю, что вы можете, но это сложное требование. На самом деле, я думаю, что это не разрешимо каким-либо эффективным образом, если они не упорядочены каким-то образом.