4

リストのリストがあり、アイテムに基づいてそれらをグループ化またはクラスター化しようとしています。ネストされたリストは、前のグループに要素がない場合、新しいグループを開始します。

入力： 

paths = [  
        ['D', 'B', 'A', 'H'],  
        ['D', 'B', 'A', 'C'],  
        ['H', 'A', 'C'],  
        ['E', 'G', 'I'],  
        ['F', 'G', 'I']]

私の失敗したコード: 

paths = [
    ['D', 'B', 'A', 'H'],
    ['D', 'B', 'A', 'C'],
    ['H', 'A', 'C'],
    ['E', 'G', 'I'],
    ['F', 'G', 'I']
]
groups = []
paths_clone = paths
for path in paths:
    for node in path:
        for path_clone in paths_clone:
            if node in path_clone:
                if not path == path_clone:
                    groups.append([path, path_clone])
                else:
                    groups.append(path)
print groups

期待される出力: 

[
 [
  ['D', 'B', 'A', 'H'],
  ['D', 'B', 'A', 'C'],
  ['H', 'A', 'C']
 ],
 [
  ['E', 'G', 'I'],
  ['F', 'G', 'I']
 ]
]

もう一つの例： 

paths = [['shifter', 'barrel', 'barrel shifter'],
         ['ARM', 'barrel', 'barrel shifter'],
         ['IP power', 'IP', 'power'],
         ['ARM', 'barrel', 'shifter']]

予想される出力グループ: 

output = [
         [['shifter', 'barrel', 'barrel shifter'],
         ['ARM', 'barrel', 'barrel shifter'],
         ['ARM', 'barrel', 'shifter']],
         [['IP power', 'IP', 'power']],
         ]
4

2 に答える 2

5

セットに基づいてグループ化しているため、セットを使用して新しいグループを検出します。

def grouper(sequence):
    group, members = [], set()

    for item in sequence:
        if group and members.isdisjoint(item):
            # new group, yield and start new
            yield group
            group, members = [], set()
        group.append(item)
        members.update(item)

    yield group

これは与える：

>>> for group in grouper(paths):
...     print group
... 
[['D', 'B', 'A', 'H'], ['D', 'B', 'A', 'C'], ['H', 'A', 'C']]
[['E', 'G', 'I'], ['F', 'G', 'I']]

または、もう一度リストにキャストできます。

output = list(grouper(paths))

これは、グループが連続していることを前提としています。ばらばらなグループがある場合は、リスト全体を処理し、これまでに作成されたすべてのグループをアイテムごとにループする必要があります。

def grouper(sequence):
    result = []  # will hold (members, group) tuples

    for item in sequence:
        for members, group in result:
            if members.intersection(item):  # overlap
                members.update(item)
                group.append(item)
                break
        else:  # no group found, add new
            result.append((set(item), [item]))

    return [group for members, group in result]
于 2013-04-30T18:06:14.430 に答える
4

Python で「グループ化しようとしています… by foo…」で始まるほとんどの質問と同様に、答えは「itertools.groupbyfoo をキーとして使用する」です。

まず、非常に単純なグループ化基準、つまり各リストの長さを考えてみましょう。そのために、キー機能はただlen. sort(データによっては、おそらく同じキーを使用して最初に行うこともできます。)

groups = [list(group) for key, group in itertools.groupby(paths, len)]

グループ化基準 (したがってキー関数) を定義することは、各要素の独立した変換という観点から定義するのが難しい、または不可能な場合があります。そのような場合、groupby一般的には答えではありません (ただしgroupby、別の関数を追加itertoolsすることもできます)。

この場合、グループ化基準を定義する最も自然な方法は、隣接する要素と比較することです。cmpこれを記述する最も簡単な方法は、隣接する 2 つの要素を比較する関数を記述し、それを使用functools.cmp_to_keyすることです。

def cmp_paths(lhs, rhs):
    return 0 if any(key in lhs for key in rhs) else -1
key_paths = functools.cmp_to_key(cmp_paths)
groups = [list(group) for key, group in itertools.groupby(paths, key_paths)]
于 2013-04-30T17:55:08.987 に答える