2

大丈夫。これは難しいかもしれませんが、私はかなり改善せずにかなり苦労しているので、皆さんの考えを知りたいです.

次のオブジェクトのリストがあるとします。

objects = [
        {'id': '1', 'w': 0.20}, 
        {'id': '1.1', 'w': 0.80}, 
        {'id': '1.2', 'w': 0.20},
        {'id': '1.3', 'w': 0.30},
        {'id': '1.1.1', 'w': 0.60},
        {'id': '1.1.2', 'w': 0.70},
        {'id': '1.1.3', 'w': 0.40},
        {'id': '1.2.1', 'w': 0.30},
    ]

このリストを「id」(例: ) で並べ替えたいのです'1', '1.1', '1.1.1', '1.1.2', '1.1.3', '1.2', '1.2.1', '1.3'が、同じ親を持つすべての要素を「w」で並べ替える必要があります (逆)。「同じ親」とはどういう意味ですか? '1' は '1.1'、'1.2'、'1.3' の親です。同様に、'1.1' は '1.1.1'、'1.1.2'、'1.1.3' の親であり、'1.2' は '1.2.1' の親です。これをよりよく説明するために、これがネストされたコメントを持つスレッドの表現であると想像してください (「1」は元の投稿、「1.1」はその回答など)。

今のところ、次のフォームに到達できました。

[ [ {'w': 0.2, 'id': '1'} ], [ {'w': 0.8, 'id': '1.1'}, {'w': 0.3, 'id': '1.3'}, 
{'w': 0.2, 'id': '1.2'} ], [ {'w': 0.7, 'id': '1.1.2'}, {'w': 0.6, 'id': '1.1.1'},
{'w': 0.4, 'id': '1.1.3'} ], [ {'w': 0.3, 'id': '1.2.1'} ] ]

ご覧のとおり、ネストされた各リストは、他の要素の子である要素で構成されています。たとえば、2 番目のネストされたリスト[ {'w': 0.8, 'id': '1.1'}, {'w': 0.3, 'id': '1.3'}, {'w': 0.2, 'id': '1.2'} ]には、 element のすべての子が含まれます[ {'w': 0.2, 'id': '1'} ]。さらに、ネストされた各リストは「w」で並べ替えられます。

最終結果は次のようになります (すべての内部リストを連鎖すると仮定すると - list(itertools.chain(*b))):

{'id': '1', 'w': 0.20}, {'id': '1.1', 'w': 0.80}, {'id': '1.1.2', 'w': 0.70}, 
{'id': '1.1.1', 'w': 0.60}, {'id': '1.1.3', 'w': 0.40}, {'id': '1.3', 'w': 0.30}, 
{'id': '1.2', 'w': 0.20},   {'id': '1.2.1', 'w': 0.30}

基本的に、最初に親、次にその子 ('w' 順) に移動し、同じことが各要素に適用されます (もちろん、子がある場合 - ここに{'id': '1.3', 'w': 0.30}は子がないため、何もする必要はありません)。それ）。

私はいくつかのことを試しました（複雑すぎて説明に値しません）。かなりの数の条件と醜いコードになってしまいました。

この並べ替えを行うにはどうすればよいですか。

前もって感謝します。

4

2 に答える 2

4

2つの要素を比較して、どちらが次の要素の前に来るかをすぐに知ることはできないため、単純な並べ替えでは問題は解決しません（親の重みによって順序が変わる場合があります）。

リストをツリー構造に処理してから、次の順序で抽出する必要があります。

tree = {}

for d in objects:
    ids = d['id'].split('.')
    w = d['w']
    # walk into the tree, creating nodes as necessary
    subtree = [0,tree]
    for n in ids:
        if n not in subtree[1]:
            subtree[1][n] = [0,{}] # w, list of nodes
        subtree = subtree[1][n] # recurse
    # subtree is now the relevant node, set w
    subtree[0] = w

## now we have a tree:
## >>> pprint.pprint(tree, width=10)
## {'1': [0.2,
##       {'1': [0.8,
##              {'1': [0.6,
##                     {}],
##               '2': [0.7,
##                     {}],
##               '3': [0.4,
##                     {}]}],
##        '2': [0.2,
##              {'1': [0.3,
##                     {}]}],
##        '3': [0.3,
##              {}]}]}

# now walk the tree and extract the nodes:
result = []
def walk_subtree(subtree, path=[]):
    keyweights = [(subtree[key][0], key) for key in subtree]
    # walk through nodes at this level, outputting.
    for weight, key in sorted(keyweights, reverse=True):
        result.append(('.'.join(path + [key]), weight))
        walk_subtree(subtree[key][1], path=path+[key])

walk_subtree(tree)

##>>> pprint.pprint(result)
##[('1', 0.2),
## ('1.1', 0.8),
## ('1.1.2', 0.7),
## ('1.1.1', 0.6),
## ('1.1.3', 0.4),
## ('1.3', 0.3),
## ('1.2', 0.2),
## ('1.2.1', 0.3)]
于 2012-05-29T06:14:11.117 に答える