0

我在 python 中有二维列表

list = [[9, 2, 7], [9, 7], [2, 7], [1, 0], [0, 5, 4]]

如果出现任何交集，我想获得列表项的联合。例如[9, 2, 7],有多个数字的交集[9, 7]。[2, 7]这将是[9,2,7].

我怎样才能以有效的方式获得最终列表如下？

finalList = [[9,2,7], [0, 1, 5, 4]]

NB 的数字顺序并不重要。

4

6 回答 6

5

这是一个理论上的答案：这是一个连通组件问题：您构建一个图如下：

  • 每个集合都有一个顶点是列表
  • 当两个集合具有共同值时，它们之间存在边。

你想要的是图的连接组件的联合。

于 2013-07-23T07:40:06.527 回答
2

你有一个图表问题。您想在图中构建连接组件，其顶点是子列表的元素，如果两个顶点是同一子列表的元素，则它们之间有一条边。您可以构建输入的邻接列表表示并在其上运行图形搜索算法，或者您可以迭代输入并构建不相交的集合。这是我为类似问题编写的稍微修改的连接组件算法：

import collections

# build an adjacency list representation of your input
graph = collections.defaultdict(set)
for l in input_list:
    if l:
        first = l[0]
        for element in l:
            graph[first].add(element)
            graph[element].add(first)

# breadth-first search the graph to produce the output
output = []
marked = set() # a set of all nodes whose connected component is known
for node in graph:
    if node not in marked:
        # this node is not in any previously seen connected component
        # run a breadth-first search to determine its connected component
        frontier = set([node])
        connected_component = []
        while frontier:
            marked |= frontier
            connected_component.extend(frontier)

            # find all unmarked nodes directly connected to frontier nodes
            # they will form the new frontier
            new_frontier = set()
            for node in frontier:
                new_frontier |= graph[node] - marked
            frontier = new_frontier
        output.append(tuple(connected_component))
于 2013-07-23T07:57:48.580 回答
1

这是一个没有任何进口的答案：

def func(L):
    r = []
    cur = set()
    for l in L:
        if not cur:
            cur = set(l)
        if any(i in cur for i in l):
            cur.update(l)
        else:
            r.append(cur)
            cur = set(l)
    r.append(cur)
    while len(r)>1:
        if any(i in r[0] for i in r[-1]):
            r[-1].update(r.pop(0))
        else:
            break
    return r

使用它：

>>> func([[9, 2, 7], [9, 7], [2, 7], [1, 0], [0, 5, 4]])
[set([9, 2, 7]), set([0, 1, 4, 5])]
>>> func([[0],[1],[2],[0,1]])
[set([2]), set([0, 1])]

您可以通过更改为来删除set并返回列表列表，但我认为返回集合更简洁。r.append(cur)r.append(list(cur))

于 2013-07-23T08:05:42.700 回答
0

这个使用集合：

>>> l = [[9, 2, 7], [9, 7], [2, 7], [1, 0], [0, 5, 4]]
>>> done = []
>>> while len(done) != len(l):
    start = min([i for i in range(len(l)) if i not in done])
    ref = set(l[start])
    for j in [i for i in range(len(l)) if i not in done]:
        if set(l[j]) & ref:
            done.append(j)
            ref |= set(l[j])
    print ref


set([2, 7, 9])
set([0, 1, 4, 5])
于 2013-07-23T07:49:32.993 回答
0

我建议您检查每对列表itertools

import itertools, numpy

ls_tmp_rmv = []

while True:
    ls_tmp = []

    for s, k in itertools.combinations(lisst, 2):
        if len(set(s).intersection( set(k) )) > 0:

            ls_tmp = ls_tmp + [numpy.unique(s + k).tolist()]

            if [s] not in ls_tmp:
                ls_tmp_rmv = ls_tmp_rmv + [s]
            if [k] not in ls_tmp:
                ls_tmp_rmv = ls_tmp_rmv + [k]
        else:
            ls_tmp = ls_tmp + [s] + [k]

    ls_tmp = [ls_tmp[i] for i in range(len(ls_tmp)) if ls_tmp[i] 
                    not in ls_tmp[i+1:]]
    ls_tmp_rmv = [ls_tmp_rmv[i] for i in range(len(ls_tmp_rmv)) 
                     if ls_tmp_rmv[i] not in ls_tmp_rmv[i+1:]]

    ls_tmp = [X for X in ls_tmp if X not in ls_tmp_rmv]

    if ls_tmp == lisst :
        break
    else:
        lisst = ls_tmp

print lisst

您获取列表中所有列表对的所有组合，并检查是否有共同的元素。如果是这样，则合并该对。如果没有，则将两个对等方添加到对中。您记住您合并的元素，以便最终将它们从结果列表中删除。

与清单

lisst = [[1,2], [2,3], [8,9], [3,4]]

你确实得到

[[1, 2, 3, 4], [8, 9]]
于 2013-07-23T13:16:30.520 回答
0 
def intersection_groups(lst):
    lst = map(set, lst)
    a, b = 0, 1
    while a < len(lst) - 1:
        while b < len(lst):
            if not lst[a].isdisjoint(lst[b]):
                lst[a].update(lst.pop(b))
            else:
                b += 1
        a, b = a + 1, a + 2
    return lst
于 2013-07-23T15:01:46.063 回答