python - 如何找到列表中的最大项目数，使得某些对在输出中不在一起？

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(items, distr_list) 从 distr_list 中删除包含 items 中任何项目的对。

def remove_from_distribute(items, distribute_list):
    new_distr = distribute_list[:]
    for item in items:
        for pair in distribute_list:
            x, y = pair
            if x == item or y == item and pair in new_distr:
                new_distr.remove((x,y))
    if new_distr:
        return new_distr
    else:
        return []

我的输出是 [4, 5, 3, 2, 1] 这显然是不正确的。你能告诉我我在这里做错了什么吗？或者你能给我一个更好的方法来解决这个问题吗？

Answer 1

我会建议另一种方法。

假设您的列表和您的分布已排序并且您的列表长度为 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]]