python - शब्दों की सूची से सबसे लंबी शब्द श्रृंखला




recursion graph (6)

इसलिए, यह एक समारोह का एक हिस्सा है जिसे मैं बनाने की कोशिश कर रहा हूं।

मैं नहीं चाहता कि कोड बहुत जटिल हो।

मेरे पास शब्दों की एक सूची है, उदाहरण के लिए

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse']

शब्द श्रृंखला अनुक्रम का विचार अगले शब्द के लिए उस अक्षर से शुरू करना है, जिसमें अंतिम शब्द समाप्त हुआ था।

(संपादित करें: प्रत्येक शब्द का उपयोग एक से अधिक बार नहीं किया जा सकता है। इसके अलावा कोई अन्य बाधा नहीं है।)

मैं चाहता हूं कि आउटपुट सबसे लंबी शब्द श्रृंखला अनुक्रम दे, जो इस मामले में है:

['hedgehog', 'giraffe', 'elephant', 'tiger', 'racoon']

मुझे वास्तव में यकीन नहीं है कि यह कैसे करना है, मुझे इसे आज़माने के अलग-अलग प्रयास थे। उनमें से एक...

यह कोड सही ढंग से शब्द श्रृंखला पाता है यदि हम सूची से एक विशिष्ट शब्द के साथ शुरू करते हैं, जैसे शब्द [0] (इसलिए 'जिराफ'):

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse']

word_chain = []

word_chain.append(words[0])

for word in words:
    for char in word[0]:

       if char == word_chain[-1][-1]:
            word_chain.append(word)

print(word_chain)

आउटपुट:

['giraffe', 'elephant', 'tiger', 'racoon']

लेकिन, मैं शब्दों की सबसे लंबी संभव श्रृंखला (ऊपर समझाया गया) खोजना चाहता हूं।

मेरी विधि: इसलिए, मैंने उपरोक्त कार्य कोड का उपयोग करने की कोशिश की, जिसे मैंने लिखा और लूप के माध्यम से, सूची से प्रत्येक शब्द को शुरुआती बिंदु के रूप में उपयोग किया और प्रत्येक शब्द के लिए शब्द श्रृंखला [0], शब्द [1], शब्द [2 ] आदि फिर मैंने एक if स्टेटमेंट का उपयोग करके सबसे लंबी वर्ड चेन खोजने की कोशिश की और लंबाई की तुलना सबसे लंबी चेन से की, लेकिन मैं इसे ठीक से नहीं कर पाया और मुझे नहीं पता कि यह कहां जा रहा है।

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse']

word_chain = []
max_length = 0
for starting_word_index in range(len(words) - 1):

    word_chain.append(words[starting_word_index])

    for word in words:
        for char in word[0]:

            if char == word_chain[-1][-1]:
                word_chain.append(word)

    # Not sure

    if len(word_chain) > max_length:
        final_word_chain = word_chain
        longest = len(word_chain)
        word_chain.clear()

print(final_word_chain)

यह मेरी कोशिश है, मुझे लगता है कि यह एक खाली सूची प्रिंट करता है, इससे पहले मेरे पास अलग-अलग प्रयास थे जो शब्द_चैन सूची को ठीक से विफल करने में विफल रहे और फिर से दोहराए गए शब्दों को समाप्त कर दिया।

किसी भी मदद की बहुत सराहना की। उम्मीद है कि मैंने इसे बहुत तीखा या भ्रमित नहीं किया ... धन्यवाद!


आप प्रत्येक "शाखा" का पता लगाने के लिए पुनरावृत्ति का उपयोग कर सकते हैं जो तब उभरती है जब उचित प्रारंभिक चरित्र वाले प्रत्येक संभावित पत्र को एक चल सूची में जोड़ा जाता है:

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse']
def get_results(_start, _current, _seen):
  if all(c in _seen for c in words if c[0] == _start[-1]):
    yield _current
  else:
      for i in words:
        if i[0] == _start[-1]:
          yield from get_results(i, _current+[i], _seen+[i])


new_d = [list(get_results(i, [i], []))[0] for i in words]
final_d = max([i for i in new_d if len(i) == len(set(i))], key=len)

आउटपुट:

['hedgehog', 'giraffe', 'elephant', 'tiger', 'racoon']

यह समाधान चौड़ाई-प्रथम खोज के समान काम करता है, क्योंकि फ़ंक्शन get_resuls पूरी सूची पर चलना जारी रखेगा जब तक कि वर्तमान मूल्य को पहले नहीं बुलाया गया हो। मान जो फ़ंक्शन द्वारा देखे गए हैं, उन्हें _seen सूची में जोड़ा जाता है, अंततः पुनरावर्ती कॉल की धारा को जारी करता है।

यह समाधान डुप्लिकेट के साथ परिणामों की भी अनदेखी करेगा:

words = ['giraffe', 'elephant', 'ant', 'ning', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse',]
new_d = [list(get_results(i, [i], []))[0] for i in words]
final_d = max([i for i in new_d if len(i) == len(set(i))], key=len)

आउटपुट:

['ant', 'tiger', 'racoon', 'ning', 'giraffe', 'elephant']

उम्मीद है, पुनरावृत्ति के बिना इसे करने का एक अधिक सहज तरीका। सूची के माध्यम से व्याख्या करें और पायथन के प्रकार और सूची की समझ को आपके लिए काम करने दें:

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse']

def chain_longest(pivot, words):
    new_words = []
    new_words.append(pivot)
    for word in words:
        potential_words = [i for i in words if i.startswith(pivot[-1]) and i not in new_words]
        if potential_words:
            next_word = sorted(potential_words, key = lambda x: len)[0]
            new_words.append(next_word)
            pivot = next_word
        else:
            pass
    return new_words

max([chain_longest(i, words) for i in words], key = len)
>>
['hedgehog', 'giraffe', 'elephant', 'tiger', 'racoon']

एक पिवट सेट करें और संभावित_शब्दों की जांच करें यदि वे आपके पिवट शब्द से शुरू होते हैं और आपके नए शब्दों की सूची में नहीं आते हैं। यदि पाया जाता है तो बस उन्हें लंबाई से क्रमबद्ध करें और पहला तत्व लें।

सूची समझ हर शब्द के माध्यम से एक धुरी के रूप में जाती है और आपको सबसे लंबी श्रृंखला लौटाती है।


जैसा कि दूसरों ने उल्लेख किया है, समस्या एक निर्देशित चक्रीय ग्राफ में सबसे लंबा रास्ता खोजना है।

पायथन से संबंधित किसी भी ग्राफ के लिए, networkx आपका मित्र है।

आपको बस ग्राफ को इनिशियलाइज़ करना है, नोड्स जोड़ना है, किनारों को जोड़ना है और dag_longest_path लॉन्च dag_longest_path :

import networkx as nx
import matplotlib.pyplot as plt

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat',
         'hedgehog', 'mouse']

G = nx.DiGraph()
G.add_nodes_from(words)

for word1 in words:
    for word2 in words:
        if word1 != word2 and word1[-1] == word2[0]:
            G.add_edge(word1, word2)
nx.draw_networkx(G)
plt.show()
print(nx.algorithms.dag.dag_longest_path(G))

यह आउटपुट:

['hedgehog', 'giraffe', 'elephant', 'tiger', 'racoon']

नोट: यह एल्गोरिथम केवल तभी काम करता है जब ग्राफ़ में कोई चक्र (लूप) न हों। इसका अर्थ है कि यह ['ab', 'ba'] साथ विफल हो जाएगा क्योंकि अनंत लंबाई का एक रास्ता होगा: ['ab', 'ba', 'ab', 'ba', 'ab', 'ba', ...]


पुनरावर्ती दृष्टिकोण का उपयोग कर एक और उत्तर:

def word_list(w_list, remaining_list):
    max_result_len=0
    res = w_list
    for word_index in range(len(remaining_list)):
        # if the last letter of the word list is equal to the first letter of the word
        if w_list[-1][-1] == remaining_list[word_index][0]:
            # make copies of the lists to not alter it in the caller function
            w_list_copy = w_list.copy()
            remaining_list_copy = remaining_list.copy()
            # removes the used word from the remaining list
            remaining_list_copy.pop(word_index)
            # append the matching word to the new word list
            w_list_copy.append(remaining_list[word_index])
            res_aux = word_list(w_list_copy, remaining_list_copy)
            # Keep only the longest list
            res = res_aux if len(res_aux) > max_result_len else res 
    return res

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse']
word_list(['dog'], words)

उत्पादन:

['dog', 'giraffe', 'elephant', 'tiger', 'racoon']

मेरे पास एक नया विचार है, जैसा कि आंकड़ा दिखाता है:

हम शब्द [0] == शब्द [-1] द्वारा निर्देशित ग्राफ का निर्माण कर सकते हैं, फिर समस्या को अधिकतम लंबाई पथ खोजने के लिए परिवर्तित किया जाता है।


यह फ़ंक्शन जनरेटर का एक प्रकार बनाता है जिसे जनरेटर कहा जाता है (देखें: "उपज" कीवर्ड क्या करता है? )। यह पुनरावर्ती सभी संभावित पूंछ अनुक्रम का पता लगाने के लिए एक ही जनरेटर के आगे के उदाहरण बनाता है:

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse']

def chains(words, previous_word=None):
    # Consider an empty sequence to be valid (as a "tail" or on its own):
    yield []
    # Remove the previous word, if any, from consideration, both here and in any subcalls:
    words = [word for word in words if word != previous_word]
    # Take each remaining word...
    for each_word in words:
        # ...provided it obeys the chaining rule
        if not previous_word or each_word.startswith(previous_word[-1]):
            # and recurse to consider all possible tail sequences that can follow this particular word:
            for tail in chains(words, previous_word=each_word):
                # Concatenate the word we're considering with each possible tail:
                yield [each_word] + tail  

all_legal_sequences = list(chains(words))  # convert the output (an iterator) to a list
all_legal_sequences.sort(key=len) # sort the list of chains in increasing order of chain length
for seq in all_legal_sequences: print(seq)
# The last line (and hence longest chain) prints as follows:
# ['hedgehog', 'giraffe', 'elephant', 'tiger', 'racoon']

या, अधिक कुशलता से सबसे लंबी श्रृंखला के लिए सीधे पाने के लिए:

print(max(chains(words), key=len)

अंत में, यहां एक वैकल्पिक संस्करण है जो इनपुट में दोहराए गए शब्दों को अनुमति देता है (यानी यदि आप एक शब्द एन बार शामिल करते हैं, तो आप इसे श्रृंखला में एन बार तक उपयोग कर सकते हैं):

def chains(words, previous_word_index=None):
    yield []
    if previous_word_index is not None:
        previous_letter = words[previous_word_index][-1]
        words = words[:previous_word_index] + words[previous_word_index + 1:]
    for i, each_word in enumerate( words ):
        if previous_word_index is None or each_word.startswith(previous_letter):
            for tail in chains(words, previous_word_index=i):
                yield [each_word] + tail  






path-finding