如何找到列表中項目的最大數目，以便某些對不在輸出中？

Question

我有一個數字

l = [1,2,3,4,5] 

的列表和描述了哪些項目不應該在輸出在一起元組的列表。

gl_distribute = [(1, 2), (1,4), (1, 5), (2, 3), (3, 4)] 

可能的名單

[1,3] 
[2,4,5] 
[3,5] 

，我想我的算法給我第二個[2,4,5]

我想遞歸地做到這一點。 在第一種情況下（t1），我用除第一個以外的所有項目調用遞歸算法，在第二種情況下（t2）我再次調用它，從gl_distribute中刪除第一個項目出現的對。 這裏是我的算法

def check_distribute(items, distribute): 
    i = sorted(items[:]) 
    d = distribute[:] 
    if not i: 
     return [] 
    if not d: 
     return i 

    if len(remove_from_distribute(i, d)) == len(d): 
     return i 

    first = i[0] 
    rest = items[1:] 
    distr_without_first = remove_from_distribute([first], d) 

    t1 = check_distribute(rest, d) 

    t2 = check_distribute(rest, distr_without_first) 
    t2.append(first) 

    if len(t1) >= len(t2): 
     return t1 
    else: 
     return t2 

的remove_from_distribute（項目，distr_list）去除distr_list包括任何在項目中的項目的對。我的輸出是[4, 5, 3, 2, 1]這顯然是不正確的。你能告訴我我在這裏做錯了嗎？或者你能給我一個更好的方法來解決這個問題嗎？

Answer 1

我不知道我完全理解你的輸出，因爲我認爲4,5和5,2應該是可能的名單，因爲他們不是在元組的列表：

如果是這樣，你可以使用itertools得到基於使用集，看是否在梳子的不同組合的任何兩個數值包含兩個元素不應該在一起gl_distribute名單上的組合和篩選，然後拿到max

combs = (combinations(l,r) for r in range(2,len(l))) 
final = [] 
for x in combs: 
    final += x 
res = max(filter(lambda x: not any(len(set(x).intersection(s)) == 2 for s in gl_distribute),final),key=len) 

print res 
(2, 4, 5) 

Answer 2

我會建議另一種方法。

假設您的列表和您的分佈已排序，並且您的列表長度爲n，並且您的分佈長度爲m。

首先，創建一個包含所有有效組合的兩個元組列表。這應該是一個O（n^2）解決方案。 一旦你有了這個列表，它只是一個通過有效組合的簡單循環並找到最長的列表。可能有更好的解決方案來進一步降低複雜性。

這裏是我的示例代碼：

def get_valid(): 
    seq = [1, 2, 3, 4, 5] 
    gl_dist = [(1, 2), (1,4), (1, 5), (2, 3), (3, 4)] 
    gl_index = 0 
    valid = [] 
    for i in xrange(len(seq)): 
    for j in xrange(i+1, len(seq)): 
    if gl_index < len(gl_dist): 
     if (seq[i], seq[j]) != gl_dist[gl_index] : 
     valid.append((seq[i], seq[j])) 
     else: 
     gl_index += 1 
    else: 
     valid.append((seq[i], seq[j])) 
    return valid 
>>>> get_valid() 
[(1, 3), (2, 4), (2, 5), (3, 5), (4, 5)] 
def get_list(): 
    total = get_valid() 
    start = total[0][0] 
    result = [start] 
    for i, j in total: 
    if i == start: 
     result.append(j) 
    else: 
     start = i 
     return_result = list(result) 
     result = [i, j] 
     yield return_result 
    yield list(result) 
    raise StopIteration 
>>> list(get_list()) 
[[1, 3], [2, 4, 5], [3, 5], [4, 5]]