合併設置迭代，如果他們有超過50％共同元素

我有一個函數，給定兩個集合A和B，它返回一個marged集合A.union（B）如果其中一個集合共享至少50％其元素與另一組，否則返回False的：合併設置迭代，如果他們有超過50％共同元素

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

現在，我想要做的就是通過一系列的列表迭代，直到列表中沒有兩套可再合併。什麼是有效的方法來做到這一點？在我看來，它看起來像一個reduce（），但實際上並不一定會減少到單個元素。

一個例子：

>>> 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

想法？

編輯 - 2016年12月4日 以防萬一，任何人都可以發現它是有用的，這是我目前工作正在進行中解決這個問題的解決方案：

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

來源

2016-12-03 Edgard Derby

當您有不同的合併路徑時，您將需要更具體地說明您想要執行的操作。例如，{0,1,2}，{1,4}，{3,4}可能變爲{0,1,2,3,4}或{0,1,2}，{1,3,4取決於合併發生的順序。 – DSM

@DSM，它並不重要。任何解決方案都被認爲是正確的，只要不可能再合併。 –

{0,1,2}，{3,4}，{0,1,2,3}就是爲什麼你不能「有效地」這樣做 - 例如與減少。 – JulienD

我認爲這是不可能的把它作爲reduce來寫，因爲操作符（reduce操作，它必須是兩個集合列表中的函數到一個集合列表）不是關聯的：「可合併」集合可以被完全不同的集合分開。如果你的輸入是有序的（即最常見元素的集合總是相鄰的），我認爲你可以，但這是一個很難的要求。實際上，我認爲它不能以任何有效的方式解決，除非這些集以某種方式排列。

來源

2016-12-04 00:40:34 JulienD

合併設置迭代，如果他們有超過50％共同元素

回答

相關問題