पायथन में जांचें कि वर्णों की आवृत्ति रिकैमन श्रृंखला में है या नहीं

मान लीजिए हमारे पास एक लोअरकेस स्ट्रिंग s है। हमें जांचना है कि s में वर्णमाला की घटनाएं, किसी भी संभावित तरीके से पुनर्व्यवस्थित करने पर, रिकैमन अनुक्रम उत्पन्न करती हैं या नहीं (पहले पद को अनदेखा करते हुए)।

रिकैमन अनुक्रम इस प्रकार है:

$$a_{n}=\begin{cases}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:0(if\:n=0) & \\a_{n-1}-n(if\:a_{n}-n>0\wedge not\:present\in sequence) & \\\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:a_{n-1}+n(otherwise)\end{cases}$$

रिकैमन अनुक्रम के कुछ आइटम हैं [0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24,...] (पहला पद अनदेखा किया गया है क्योंकि यह 0 है)

इसलिए, यदि इनपुट s = "pppuvuuqquuu" है, तो आउटपुट True होगा क्योंकि वर्ण और आवृत्तियां (p, 3), (u, 6), (v, 1) और (q, 2) हैं। तो आवृत्तियां रिकैमन अनुक्रम के पहले कुछ पदों [1, 3, 6, 2] का निर्माण कर रही हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

• freq := s में सभी वर्णों और उनकी आवृत्तियों को रखने वाला मैप
• n := freq का आकार
• array := पहले n रिकैमन अनुक्रम पद
• f := 1
• freq में प्रत्येक char के लिए, करें
  • is_found := 0
  • j के लिए 1 से n तक की रेंज में, करें
    • यदि freq[keys], array[j] के समान है, तो
      • is_found := 1
      • लूप से बाहर आएं
  • यदि is_found गलत है, तो
    • f := 0
    • लूप से बाहर आएं
• True लौटाएं जब f सेट हो अन्यथा False

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

from collections import defaultdict
def recaman(array, n):
    array[0] = 0
    for i in range(1, n + 1):
        temp = array[i - 1] - i
        for j in range(i):
            if array[j] == temp or temp < 0:
                temp = array[i - 1] + i
                break
        array[i] = temp
def solve(s):
    freq = defaultdict(int)
    for i in range(len(s)):
        freq[s[i]] += 1
    n = len(freq)
    array = [0] * (n + 1)
    recaman(array, n)
    f = 1
    for keys in freq.keys():
        is_found = 0
        for j in range(1, n + 1):
            if freq[keys] == array[j]:
                is_found = 1
                break
        if not is_found:
            f = 0
            break
    return True if f else False
s = "pppuvuuqquuu"
print(solve(s))

इनपुट

"pppuvuuqquuu"

आउटपुट

True