सर्च कर रहे हैं एल्गोरिथ्म

Question

मैं एक कुशल खोज एल्गोरिथ्म के लिए देख रहा हूँ एक संग्रह (~ पूर्णांकों का 2k), जहाँ मेरे संग्रह केवल इस दोहराया पैटर्न से बना है में सबसे लंबे समय तककम से कम दोहराया पैटर्न प्राप्त करने के लिए (कोई शोर है दोहराए गए पैटर्न के बीच), लेकिन पैटर्न की आखिरी घटना अधूरा हो सकती है।

उदाहरण: मुझे मिल गया है: [2,4,1, 2,4,1, 2,4,1, 2,4,1, 2,4,1]
मैं करना चाहते हैं recieve: [2,4,1]

मुझे मिल गया है: [21,1,15,22, 21,1,15,22, 21,1,15,22, 21,1,15]
मैं करना चाहते हैं recieve: [21,1,15,22]

मुझे मिल गया है: [3,2,3,2,5]
मैं प्राप्त करने के लिए करना चाहते हैं: [] (कोई पैटर्न है)

(रिक्त स्थान के लिए केवल रिक्त स्थान जोड़े गए हैं)

Answer 1

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

def check(a, width): 
    '''check if there is a repeated pattern of length |width|''' 
    for j in range(width, len(a)): 
    if a[j] != a[j-width]: 
     return False 
    return True 

def repeated(a): 
    '''find the shortest repeated pattern''' 
    for width in range(1, len(a)): 
    if check(a, width): 
     return a[:width] 
    return [] 

यह भी है, बल्कि कुशल होना चाहिए समय में पाश के सबसे बाद से check() पहले पुनरावृत्ति में ठीक से वापस आ जाएगा, ताकि आप मूल रूप से केवल एक बार सूची में फिर से चालू हो जाएं।

Answer 2

समूह में पहली संख्या के समान होने तक समूह में एक संख्या जोड़ने तक प्रारंभिक शुरुआत से अपना प्रारंभिक समूह बनाने का प्रयास करें (पिछली संख्या समाप्त हो जाती है पैटर्न)। इसे अपने परीक्षण पैटर्न के रूप में उपयोग करें और जब तक आपको विफलता न हो तब तक पैटर्न से मिलान करें। यदि आप पूरे संग्रह से मेल खाते हैं (आपके विशेष अंत पैटर्न हैंडलिंग के साथ) जो एक उम्मीदवार है। उस स्थान पर वापस जाएं जहां आपको अपना प्रारंभिक मिलान मिला, फिर अपने समूह को तब तक जारी रखें जब तक कि आप अपने पैटर्न में पहले से मेल खाने वाले दूसरे नंबर पर न आएं। जब भी आपको एक लंबा लगता है तो अपने उम्मीदवार को दोहराएं। जब आपका पैटर्न संग्रह स्टॉप के समान लंबाई होता है (यह कोई मेल नहीं खाता है)। यदि आपके पास कोई उम्मीदवार है जो सबसे लंबा पैटर्न होगा।

Answer 3

मुझे लगता है कि आप पैटर्न की अवधि पर विचार करके इस समस्या से संपर्क कर सकते हैं। अनुक्रम ए की अवधि ए [] सबसे छोटा पूर्णांक टी है जैसे कि ए [i + टी] = ए [i] सभी के लिए। आपके मामले में, जब आपको टी अवधि मिलती है, तो आप कर चुके हैं, क्योंकि ए [0..टी -1] वह सबसे छोटा पैटर्न है जिसे आप ढूंढ रहे हैं। तो, छोटी अवधि के साथ शुरू करें टी = 1 और परीक्षण करें कि अनुक्रम आवधिक संपत्ति को संतुष्ट करता है। यदि हां, तो आप कर चुके हैं (यह वास्तव में तब होता है जब सभी तत्व समान होते हैं)। किसी भी बड़े टी के लिए, आपको यह जांचने की आवश्यकता है कि ए [i + T] = ए [i] i = 0..A.len-T-1 के लिए। यह सिर्फ एक साधारण पाश है।

Answer 4

आप यह देखकर ऑप्टिमाइज़ कर सकते हैं कि आपके संग्रह की लंबाई आपकी पैटर्न लंबाई का एक बहु होना चाहिए। यदि आपके संग्रह में एक आकार है जो प्राइम है, तो केवल संभावित पैटर्न लंबाई 1 है, यानी सभी तत्व समान होना चाहिए!