合并设置迭代，如果他们有超过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％共同元素

回答

相关问题