嵌套列表，检查一个列表是否与另一个列表有共同的元素，如果有，则合并

Question

我有一个列表嵌套列表，例如 [[1, 3, 5], [2, 4], [1,7,9]]

我的要求是遍历这个列表并将其缩减为

[[1,3,5,7,9], [2,4]].

我该怎么做呢？

- DeadDjangoDjoker

---

减少它的标准是什么？奇数和偶数吗？ - Tim

你为什么要合并列表1和3？只是因为它们共享元素“1”吗？ - Tim

@ tim 是的，如果它们有共同的元素，我想要合并它们。 - DeadDjangoDjoker

你可能想提供不止一个例子吗？ - st0ne

@DeadDjangoDjoker：这个 [[1,2], [3,4 ], [1,5,3], [5]] 的输出结果会是什么？ - Vivek Sable

Answer 1

这很低效，但它能达到效果：

def combine_lists(lists):
    # Keep a set of processed items
    skip = set()

    for i, a in enumerate(lists):
        # If we already used this list, skip it
        if i in skip:
            continue

        for j, b in enumerate(lists[i + 1:], i + 1):
            # Use a set to check if there are common numbers
            if set(a) & set(b):
                skip.add(j)

                for x in b:
                    if x not in a:
                        a.append(x)

    # yield all lists that were not added to different lists
    for i, a in enumerate(lists):
        if i not in skip:
            yield a

[编辑] 刚刚注意到顺序不再重要（您的输出表明它很重要），这使得事情变得更加容易 :)

这个版本应该是相当优化的：

def combine_lists(lists):
    # Keep a set of processed items
    skip = set()
    sets = map(set, lists)

    for i, a in enumerate(sets):
        # If we already returned this set, skip it
        if i in skip:
            continue

        for j, b in enumerate(sets[i + 1:], i + 1):
            # Use a set to check if there are common numbers
            if a & b:
                skip.add(j)
                a |= b

    # yield all sets that were not added to different sets
    for i, a in enumerate(sets):
        if i not in skip:
            yield a

- Wolph

---

尝试了这个...对我似乎没有用:(...不管怎样，谢谢:) - DeadDjangoDjoker

第一种解决方案似乎运行良好，但第二种则不行：http://ideone.com/qFU86M - Ashwini Chaudhary

@AshwiniChaudhary：哎呀...看来我复制时犯了一个错误，最后的“lists”应该是“sets”。谢谢你提醒我 :) - Wolph

Answer 2

算法：

1. 从新方法中获取基本元素。
2. 从输入列表中删除第一个项目并为其创建新变量。
3. 对新列表中的每个项目进行迭代。
4. 通过集合intersection方法检查项目中的任何元素是否存在于基本集中。
5. 如果存在，则执行6,7,8,9步骤
6. 使用集合update方法将当前项目更新为基本项目。
7. 从列表中删除当前项目。
8. 设置标志为True。
9. 中断for循环，因为需要再次从第一个项目进行检查。
10. 创建最终结果列表，添加基本列表和剩余列表。

[编辑:]

问题:

以前的代码将基本项视为给定列表中的第一项，但当此项与其他项没有匹配而其他项具有匹配时，代码将无效。

更新:

从给定列表中获取具有与列表中任何一项匹配的基本项。

[编辑2]:

将合并后的项目插入到相应的位置

演示：

import copy

a = [[13, 15, 17], [66,77], [1, 2, 4], [1,7,9]]

#- Get base
base = None
length_a = len(a)
base_flag = True
i = -1
while base_flag and i!=length_a-1:
    i += 1
    item = a[i]
    for j in xrange(i+1, length_a):
        tmp = set(item).intersection(set(a[j]))
        if tmp:
            base = set(item)
            base_flag = False
            break

print "Selected base:", base
if base:
    tmp_list = copy.copy(a)
    target_index = i
    tmp_list.pop(target_index)
    flag = True
    while flag:
        flag = False
        for i, item in enumerate(tmp_list):
            tmp = base.intersection(set(item))
            if tmp:
                base.update(set(item))
                tmp_list.pop(i)
                flag = True
                break

    print "base:", base
    print "tmp_list:", tmp_list
    result = tmp_list
    result.insert(target_index, list(base))

else:
    result = a

print "\nFinal result:", result

输出：

$ python task4.py 
Selected base: set([1, 2, 4])
base: set([1, 2, 4, 7, 9])
tmp_list: [[13, 15, 17], [66, 77]]

Final result: [[13, 15, 17], [66, 77], [1, 2, 4, 7, 9]]

- Vivek Sable

---

工作正常:)...谢谢:) - DeadDjangoDjoker

不确定为什么这个回答会有四个upvotes和一个采纳(@DeadDjangoDjoker)，因为它并不起作用：http://ideone.com/PTMJvr. 另外请注意，大多数集合方法（例如交集，更新等）都可以与任何可迭代对象一起正常使用，因此无需将其转换为集合。 - Ashwini Chaudhary

@AshwiniChaudhary：现在检查一下，更新了，请让我知道是否有更多改进或者对于其他测试用例不起作用？ - Vivek Sable

@AshwiniChaudhary 我刚刚测试了一下我的条件，它起作用了，但是你说的没错，在其他条件下它失败了。 - DeadDjangoDjoker

@VivekSable...我会检查并告诉你...谢谢:) - DeadDjangoDjoker

Answer 3

a = [[1,2], [3,4 ], [1,5,3], [5]] # output: [set([1, 2, 3, 4, 5])]
# a = [[1, 3, 5], [2, 4], [1,7,9]] # output: [set([1, 3, 5, 7, 9]), set([2, 4])]

# convert them to sets
a = [set(x) for x in a]
go = True

while go:
    merged = False
    head = a[0]

    for idx, item in enumerate(a[1:]):
        if head.intersection(item):
            a[0] = head.union(item)
            a.pop(idx + 1)
            merged = True
            break

    if not merged:
        go = False

print a

- MK Yung