50％以上の要素が共通している場合、マージは繰り返し設定されます

Question

2つのセットAとBを指定すると、その2つのセットのいずれかが50％他のセット、そうでなければFalseとその要素の：今

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 

Answer 1

私はそれをすることはできないと思います（2つのセットのリストからセットのリストへの関数でなければならないreduceオペレーション）は結合的ではないので、それをreduceとして書く：「マージ可能な」セットは完全に異なるセットで区切ることができる。入力を注文した場合（最も一般的な要素が常に隣接しているセット）は可能ですが、難しい要件です。実際には、セットが何らかの方法で順序付けされていないと効率的な方法で解決できないと私は思っています。