পাইথনের রেকাম্যান সিরিজে অক্ষরের ফ্রিকোয়েন্সি আছে কিনা তা পরীক্ষা করুন

ধরুন আমরা একটি ছোট হাতের স্ট্রিং s আছে. আমাদের পরীক্ষা করতে হবে s-এ বর্ণমালার উপস্থিতি, যেকোনো সম্ভাব্য পদ্ধতিতে পুনর্বিন্যাস করার পরে, রেকম্যানের সিকোয়েন্স তৈরি করে (প্রথম শব্দটিকে উপেক্ষা করে)।

Recaman এর ক্রম নিম্নরূপ -

$$a_{n}=\begin{cases}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:0(if\:n=0 ) &\\a_{n-1}-n(if\:a__{n}-n>0\wedge not\:present\in ক্রমানুসারে) &\\\:\:\:\:\:\:\ :\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:a_{n-1}+n(অন্যথায়)\end{কেস }$$

রেকাম্যানের সিকোয়েন্সের কিছু আইটেম হল [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 :=ফ্রিকোয়েন্সির আকার
অ্যারে :=প্রথম n রেকাম্যানের ক্রম পদ
f :=1
ফ্রিকে প্রতিটি অক্ষরের জন্য, করুন
- is_found :=0
- করুন
  - যদি freq[keys] array[j] এর মত হয়, তাহলে
    - is_found :=1
    - লুপ থেকে বেরিয়ে আসুন
- যদি is_found মিথ্যা হয়, তাহলে
  - f :=0
  - লুপ থেকে বেরিয়ে আসুন
সত্য ফেরত দিন যখন 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