chuỗi dài nhất của các yếu tố từ danh sách bằng Python

Question

tôi có một danh sách của các quốc gia, và tôi muốn có con đường dài nhất của các quốc gia trong đó mỗi quốc gia được chọn phải bắt đầu bằng chữ giống như kết thúc phần tử trước

nations = ['albania','andorra','austria','belarus','belgium','bosnia and herzegovina', 
     'bulgaria','croatia','czech republic','denmark','estonia', 
     'finland','france','germany','greece','hungary', 
     'iceland','ireland','italy','latvia','liechtenstein','lithuania','luxembourg', 
     'macedonia','malta','moldova','monaco','montenegro','netherlands', 
     'norway','poland','portugal','romania','russia', 
     'san marino','serbia','slovakia','slovenia','spain','sweden', 'switzerland', 
     'ukraine','united kingdom','vatican city'] 

chain('spain') 
>>>['spain', 'netherlands', 'slovenia', 'andorra', 'austria', 'albania'] 

Tôi đã thử cách này, nhưng nó không hoạt động

def chain(naz): 
    initial = naz[-1] 
    initials=[] 
    res = set() 
    res.add(naz) 
    for i in nations: 
     if i.startswith(initial): 
      initials.append(i) 
    for j in initials: 
     nations.remove(j) 
     res.add(j) 
     chain(j) 
    return res 

Bất kỳ đề xuất nào?

Answer 1

Tôi cũng đã đi cho đệ quy gốc. Bạn không chắc liệu lập trình động có phù hợp với điều này vì danh sách được sửa đổi khi chúng ta đi. Hơi nhỏ gọn hơn và không cần phải bắt đầu xóa khỏi danh sách trước khi gọi chuỗi. :-)

def chain(start, countries): 
    remaining = list(countries) 
    del remaining[remaining.index(start)] 
    possibles = [x for x in remaining if x[:1] == start[-1:]] 
    maxchain = [] 
    for c in possibles: 
     l = chain(c, remaining) 
     if len(l) > len(maxchain): 
      maxchain = l 
    return [start] + maxchain 

Gọi như thế này. :-)

>>> chain('spain', nations) 
['spain', 'netherlands', 'serbia', 'albania', 'andorra', 'austria'] 

Answer 2

Dưới đây là một số ý kiến:

• bạn muốn trả về một con đường. Vì vậy, nó là một bộ sưu tập theo yêu cầu phải không? Có thể bạn không nên sử dụng tập hợp để đặt lại, vì tập hợp không được đặt trước
• bạn có biết chiều dài hoặc đường dẫn được trả lại không? Không bạn không. Vì vậy, bạn có thể cần một số while ở đâu đó
• i.startswith(initial) là đúng chỉ khi tôi bắt đầu với toàn bộ từ ban đầu. Có thể bạn không muốn điều này
• bạn cố gắng sử dụng một cách tiếp cận lặp lại. Tuy nhiên bạn không thu thập kết quả. Cuộc gọi recurcive là vô ích cho thời điểm này
• nations là một biến toàn cầu, đó là xấu

chỉnh sửa

Các lỗi được mô tả trong bình luận của bạn có thể xảy ra vì cuộc gọi recurcive của bạn là bên trong k vòng lặp . Cuộc gọi lặp lại có thể loại bỏ các yếu tố cho các quốc gia, cũng có thể tồn tại trong các chữ cái đầu. Vì vậy, bạn đang cố gắng loại bỏ chúng nhiều lần, điều này làm tăng ngoại lệ. Bạn có thể có nghĩa là đặt chain(j) bên ngoài vòng lặp (và có thể sử dụng giá trị trả về của nó?)

Answer 3

đây là một cách tiếp cận đệ quy ngây thơ ... tôi cảm thấy như bạn có thể sử dụng lập trình năng động và nó sẽ là tốt hơn

def chain(start,options): 
    #start is the starting word 
    #options are the words left 

    next_options = [country for country in options if country[0] == start[-1]] 

    #if theres no options, return the single 
    if not next_options: 
     return [start] 

    #otherwise, return best chain out of the next option 
    best_chain = None 
    longest_chain = 0 

    for option in next_options: 

     new_options = options[:] 
     new_options.remove(option) 

     possible_chain = chain(option,new_options) 

     if len(possible_chain) > longest_chain: 
      best_chain = possible_chain 
      longest_chain = len(possible_chain) 

    return [start] + best_chain 

Answer 4

Là một mặt lưu ý, vấn đề của bạn là NP-đầy đủ (có nghĩa là nó không có "nhanh" giải pháp thời gian đa thức.) Đó là khả năng giải quyết cho các kích cỡ vấn đề nhỏ, nhưng nó được rất khó khăn rất nhanh chóng.

Sự cố của bạn có thể được coi là longest-path problem on a directed graph.

• Vẽ directed graph với mỗi từ (quốc gia) được biểu thị dưới dạng đỉnh.
• Đối với mỗi cặp từ, w1 và w2, vẽ cạnh w1 -> w2 nếu chữ cái cuối cùng của w1 giống như chữ cái đầu tiên của w2.
• Đồng thời vẽ cạnh trái từ w2->w1 nếu chữ cái cuối cùng của w2 s giống với chữ cái đầu tiên của w1.
• Tìm số maximum-length path - đường dẫn đơn giản chứa số lượng đỉnh nhiều nhất. ("Đơn giản" trong trường hợp này có nghĩa là "không bao gồm bất kỳ đỉnh nhiều lần.")

Dưới đây là một biểu đồ ví dụ cho một danh sách các loại trái cây và rau quả: Apple, banana, eggplant, kiwifruit, orange, oregano, tangerine, zucchini.

Biểu đồ này có thể chứa những chu kỳ (ví dụ, đồ thị này có một chu kỳ eggplant -> tangerine -> eggplant -> tangerine..... The longest path problem for directed graphs containing cycles is NP-complete. Vì vậy không có giải pháp đa thức thời gian cho vấn đề này.

này không có nghĩa là bạn có thể' t làm tốt hơn brute force. There's a dynamic programming algorithm làm giảm sự phức tạp từ O(n!) (thừa, rất xấu) để O(n^2 * 2^n) (superexponential, vẫn còn xấu, nhưng tốt hơn so với giai thừa.)