沒有遞歸的字典中鍵值對的最長週期

我對字典有疑問。我想知道如何解決這個問題，而不使用遞歸函數（因爲這是一個要求）。該代碼創建一個隨機字典，名稱列表中的名稱相互連接。我知道代碼應該做什麼，但不知道如何做到這一點。沒有遞歸的字典中鍵值對的最長週期

我需要開始鍵，我成功提取（可能以不正確/醜陋的方式）。然後，代碼應該循環整個循環，如代碼底部的引號所示，直到開始鍵再次被找到爲一個值。循環應該結束並返回此循環的長度。

下面的代碼是我設法提出的，即使它是錯誤的。我寧願回答沒有遞歸函數如前所述。

from random import seed, choice 
import time 
seed(0) 
nameslist = [ "Liam", "Emma", "Noah", "Olivia", ] 


# Creates random couples dictionary from a list 
def create_dictionary(nlist): 
    dict = {} 
    nlistcopy = nlist[:] 
    for item in nlist: 
     dict[item] = choice(nlistcopy) 
     nlistcopy.remove(dict[item]) 
    return dict 

# Generates the longest cycle in the couples dictionary, however, the code does not seem to work. 

def longest_cycle(dict): 
    longest = 0 
    for each in dict: 
     start = dict[each] 
     break 
    each = 0 
    while each != start : 
     for each in dict: 
      each = dict[each] 
      print(each) 
      longest += 1 
     time.sleep(5) 


namesdict = create_dictionary(nameslist) 
print(longest_cycle(namesdict)) 

# Dictionary = {'Liam': 'Olivia', 'Noah': 'Liam', 'Olivia': 'Noah', 'Emma': 'Emma'} 
# Liam --> Olivia --> Noah --> Liam (longest cycle = 3)!

最終的名稱列表將包含更多的名稱，這個較短的版本僅用於測試目的。休眠時間是爲了防止無限循環崩潰我的筆記本（我使用Jupyter筆記本來解決問題）。提前致謝！

來源

2016-12-21 Menno Van Dijk

[按連續順序對元組列表進行排序]可能的副本（http://stackoverflow.com/questions/41221428/sort-a-list-of-tuples-in-consecutive-order） –

我沒有認爲是這樣，這看起來更像是DFS – Har

您需要從類似於上述重複的每個關鍵字開始查找連續字典的列表。用計數器映射每個密鑰的路徑。最後，你可以提取基於計數器的路徑 –

我不知道是否有更好的解決辦法，但無論如何，這是非常簡單的，不使用任何遞歸函數：

dict = {'Liam': 'Olivia', 'Noah': 'Liam', 'Olivia': 'Noah', 'Emma': 'Emma'} 

result = 0 
longest = 1 # longest_cycle of a key, always == 1 at first 

for key in dict.keys(): 
    dest = key 
    key = dict[key] 
    while dest != key: 
     key = dict[key] 
     longest += 1 
    if longest > result: 
     result = longest 
    longest = 0 

print(result)

來源

2016-12-21 11:35:47

杉杉的事情避免命名dict這是一個保留字就像list ，第二讓我們簡化代碼：

import random 

def create_names_dict(names_list): 
    names_list_random = names_list[:] 
    random.shuffle(names_list_random) 
    return {k:v for k,v in zip(names_list, names_list_random)}

下一步：

def longest_cycle(names_list, names_dict): 
    start = names_list[0] 
    key = start 
    value = names_dict[start] 
    longest = [start] 
    while start != value: 
     longest.append(value) 
     key, value = value, names_dict[value] 
    longest.append(value) 
    print('%s (longest cycle: %d)' % (' --> '.join(longest), len(longest) - 1))

測試：

>>> names_list = [ "Liam", "Emma", "Noah", "Olivia", ] 
>>> names_dict = create_names_dict(names_list) 
>>> names_dict 
{'Noah': 'Noah', 'Liam': 'Emma', 'Olivia': 'Liam', 'Emma': 'Olivia'} 
>>> longest_cycle(names_list, names_dict) 
Liam --> Emma --> Olivia --> Liam (longest cycle: 3)

乾杯！

來源

2016-12-21 12:00:53 Saksow

沒有遞歸的字典中鍵值對的最長週期

回答

相關問題