某些情況下的「困難」排序

好的。這可能很困難，但我一直在努力掙扎，但沒有得到很大的改善，所以我想知道你們的想法。某些情況下的「困難」排序

假設我有以下對象名單：

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

我想通過「身份證」（例如'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'} ] ]

正如你所看到的，每個嵌套列表包括其他元素的子元素。例如，第二個嵌套列表[ {'w': 0.8, 'id': '1.1'}, {'w': 0.3, 'id': '1.3'}, {'w': 0.2, 'id': '1.2'} ]包含元素[ {'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}沒有孩子，所以我們不需要對它做任何事情）。

我已經嘗試了一些事情（太複雜，值得解釋）。我結束了很多條件和一個醜陋的代碼。

我該如何完成這個排序？

在此先感謝。

來源

2012-05-29 Robert Smith

你張貼了預期的效果樣品沒有排序按你的描述。例如，「1.1.2」在「1.1.1」之前; 'w'是任意排序的。 –

@BurhanKhalid w按照相反順序排列，如果仔細觀察，結果確實有意義。 – jamylak

@BurhanKhalid是的，正如jamylak所說，1.1.2之前是因爲它是1.1的孩子，所以按照我的描述，它們應該用'w'（前0.70，然後0.60）排序。對不起，我錯過了這個澄清。 –

簡單的排序不會解決您的問題，因爲無法比較任何兩個元素，並立即知道何時一個接一個（父母的權重可能會改變排序）。

你需要處理的列表爲樹狀結構，然後才能提取它：

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-29 06:14:11 jnnnnn

@jnnnnn這看起來不錯，雖然正如我在其他答案中所說的那樣，我是在避開樹來排序答案。至少，這是在沒有去數據庫的情況下完成的。我會在幾個小時內看看你的代碼（這裏有點晚），但非常感謝你:-)。 –

@RobertSmith - 我不認爲你*可以*避免某種形式的樹或樹狀結構，因爲你試圖做的是基於樹的基礎（父母/孩子/等）。 – weronika

@jnnnnn我對這個解決方案印象非常深刻。讓我問你，這是一個標準程序嗎？似乎它使用了字典通過引用傳遞來構造樹，同時實際修改子樹的事實。它也暴露子樹中的列表以改變該節點的權重，並且由於列表也是可變的，所以這些改變在樹中執行。當然你在考慮檢查節點並創建它們，如果它們不存在但它並不那麼簡單。我需要仔細看看walk_subtree的某些部分，但正如我所說，非常好的解決方案。 –

用比較器排序。也就是說，你寫一個方法看起來像

def comparator(x, y): 
    ## some code that sets value to -1 if x is "less than" y 
    ## or 1 if x is "greater than or equal to" y. 
    return value

然後調用objects.sort(comparator)，你應該設置。

這種方式你只需要處理一次比較兩個項目。只要你一致，這應該不成問題。

來源

2012-05-29 06:06:51

然後當你移動到3.x它會炸燬，因爲3.x不支持比較器。 –

@ IgnacioVazquez-Abrams不是每個人都打算遷移到3，不僅僅是因爲它不必要地刪除了這樣的功能。 – Marcin

@ IgnacioVazquez-Abrams 3.x的意思是不支持比較器？禁止性的高時間需要貫穿所有元素？ –

某些情況下的「困難」排序

回答

相關問題