0

私はPythonで2Dリストを持っています

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]]

注: 番号の順序は重要ではありません。

4

6 に答える 6

5

理論的な答えは次のとおりです。これは連結成分の問題です。次のようにグラフを作成します。

  • 各セットの頂点がリストです
  • 2 つのセットに共通の値がある場合、それらの間にエッジがあります。

必要なのは、グラフの接続されたコンポーネントの結合です。

于 2013-07-23T07:40:06.527 に答える
2

グラフの問題があります。頂点がサブリストの要素であり、2 つの頂点が同じサブリストの要素である場合、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 に答える
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 に答える
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

これはセットを使用します：

>>> 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 に答える