2

タプルのリストがあります。[ (1, 2), (2, 3), (4, 3), (5, 6), (6, 7), (8, 2) ]

どのタプルが接続されているか (関連する値があるか) に基づいて、それらをリストにグループ化したいと考えています。

したがって、最終結果は、関連するタプル値の 2 つのリスト = [ [1, 2, 3, 4, 8], [5, 6, 7] ] になります。

これを行う関数をどのように書くことができますか? これは就職面接の質問でした。私はPythonでそれをやろうとしていましたが、私はイライラしていて、答えの背後にあるロジックを見たいだけなので、疑似コードでも助けになるので、何が間違っていたのかがわかります.

その場でこれを行うのに数分しかありませんでしたが、私が試したことは次のとおりです。

def find_partitions(connections):
 theBigList = []     # List of Lists
 list1 = []          # The initial list to store lists
 theBigList.append(list1)

 for list in theBigList:
 list.append(connection[1[0], 1[1]])
     for i in connections:
         if i[0] in list or i[1] in list:
             list.append(i[0], i[1])

         else:
             newList = []
             theBigList.append(newList)

本質的に、男は関連する値のリストのリストを望んでいました。for ループを使用しようとしましたが、機能しないことに気付き、時間切れになりました。

4

5 に答える 5

2

コンポーネントを入力する際、各段階で考慮すべき 3 つのケースがあります (重複するグループを一致させる必要があるため)。

  1. x も y も、既に見つかったコンポーネントにはありません。
  2. 両方とも既に異なるセットにあり、x は set_i に、y は set_j にあります。
  3. いずれかまたは両方が 1 つのコンポーネントにあり、x が set_i にあるか、y が set_i にあります。

ビルトインを使用して支援できsetます。(@jwpat と @DSM のトリッキーな例を参照してください) :

def connected_components(lst):
    components = [] # list of sets
    for (x,y) in lst:
        i = j = set_i = set_j = None
        for k, c in enumerate(components):
            if x in c:
                i, set_i = k, c
            if y in c:
                j, set_j = k, c

        #case1 (or already in same set)
        if i == j:
             if i == None:
                 components.append(set([x,y]))
             continue

        #case2
        if i != None and j != None:
            components = [components[k] for k in range(len(components)) if k!=i and k!=j]
            components.append(set_i | set_j)
            continue

        #case3
        if j != None:
            components[j].add(x)
        if i != None:
            components[i].add(y)

    return components               

lst = [(1, 2), (2, 3), (4, 3), (5, 6), (6, 7), (8, 2)]
connected_components(lst)
# [set([8, 1, 2, 3, 4]), set([5, 6, 7])]
map(list, connected_components(lst))
# [[8, 1, 2, 3, 4], [5, 6, 7]]

connected_components([(1, 2), (4, 3), (2, 3), (5, 6), (6, 7), (8, 2)])
# [set([8, 1, 2, 3, 4]), set([5, 6, 7])] # @jwpat's example

connected_components([[1, 3], [2, 4], [3, 4]]
# [set([1, 2, 3, 4])] # @DSM's example

これは確かに最も効率的な方法ではありませんが、おそらく彼らが期待する方法に似ています。Jon Clements が指摘しているように、これらのタイプの計算にはnetworkxというライブラリがあり、より効率的です。

于 2012-12-10T20:51:53.057 に答える
1 
l = [ (1, 2), (2, 3), (4, 3), (5, 6), (6, 7), (8, 2) ]

# map each value to the corresponding connected component
d = {}
for i, j in l:
  di = d.setdefault(i, {i})
  dj = d.setdefault(j, {j})
  if di is not dj:
    di |= dj
    for k in dj:
      d[k] = di

# print out the connected components
p = set()
for i in d.keys():
  if i not in p:
    print(d[i])
  p |= d[i]
于 2012-12-10T20:57:06.063 に答える
0

使用sets:

In [235]: def func(ls):
    new_lis=sorted(sorted(ls),key=min) 
    lis=[set(new_lis[0])]
    for x in new_lis[1:]:
            for y in lis:
                    if not set(x).isdisjoint(y):
                            y.update(x);break 
            else:lis.append(set(x))
    return lis
   .....: 

In [236]: func([(3, 1), (9, 3), (6, 9)])
Out[236]: [set([1, 3, 6, 9])]

In [237]: func([[2,1],[3,0],[1,3]])
Out[237]: [set([0, 1, 2, 3])]

In [239]: func([(1, 2), (4, 3), (2, 3), (5, 6), (6, 7), (8, 2)])
Out[239]: [set([8, 1, 2, 3, 4]), set([5, 6, 7])]
于 2012-12-10T20:56:31.543 に答える
0

どうですか

ts = [(1, 2), (2, 3), (4, 3), (5, 6), (6, 7), (8, 2)]
ss = []
while len(ts) > 0:
    s = set(ts.pop())
    ol = 0
    nl = len(s)
    while ol < nl:
        for t in ts:
            if t[0] in s or t[1] in s: s = s.union(ts.pop(ts.index(t)))
        ol = nl
        nl = len(s)
    ss.append(s)

print ss
于 2013-09-12T04:37:33.917 に答える
0

これは確かにエレガントではありませんが、機能します。

def _grouper(s,ll):
    for tup in ll[:]:
        if any(x in s for x in tup):
            for y in tup:
                s.add(y)
                ll.remove(tup)

def grouper(ll,out=None):
    _ll = ll[:]
    s = set(ll.pop(0))
    if out is None:
        out = [s]
    else:
        out.append(s)

    l_old = 0
    while l_old != len(_ll):
        l_old = len(_ll)
        _grouper(s,_ll)

    if _ll:
        return grouper(_ll,out=out)
    else:
        return out

ll = [ (1, 2), (2, 3), (4, 3), (5, 6), (6, 7), (8, 2) ]
print grouper(ll)
于 2012-12-10T20:51:34.053 に答える