मान लीजिए कि हमारे पास एक लोअरकेस स्ट्रिंग s है। हमें यह जांचना होगा कि किसी भी संभावित तरीके से पुनर्व्यवस्थित करने के बाद, s में वर्णों की पुनरावृत्ति, रिकामन का अनुक्रम उत्पन्न करती है (पहले पद को अनदेखा करते हुए)।
रिकामन का क्रम इस प्रकार है -
$$a_{n}=\ start{cases}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:0(अगर\:n=0 ) और \\a_{n-1}-n(if\:a_{n}-n>0\wedge not\:वर्तमान\क्रम में) और \\\:\:\:\:\:\:\ :\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:a_{n-1}+n(अन्यथा)\end{मामलों }$$
रिकामन के अनुक्रम के कुछ पद हैं [0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24,...] (पहला पद है अनदेखा किया गया क्योंकि यह 0 है)
इसलिए, यदि इनपुट s ="pppuvuuqquuu" जैसा है, तो आउटपुट सही होगा क्योंकि वर्ण और आवृत्तियाँ (p, 3), (u, 6), (v, 1) और (q, 2) हैं। अतः आवृत्तियाँ रिकामन के अनुक्रम [1, 3, 6, 2] के पहले कुछ पद बना रही हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- freq:=सभी वर्णों को s और उनकी आवृत्तियों में रखने वाला नक्शा
- n :=आवृत्ति का आकार
- सरणी :=पहले n रिकामन के अनुक्रम की शर्तें
- f :=1
- फ़्रीक में प्रत्येक चार के लिए, करें
- is_found :=0
- जे के लिए 1 से n तक, करें
- यदि freq[कुंजी] सरणी [j] के समान है, तो
- is_found :=1
- लूप से बाहर आएं
- यदि freq[कुंजी] सरणी [j] के समान है, तो
- अगर is_found गलत है, तो
- f :=0
- लूप से बाहर आएं
- जब f सेट हो तो सही लौटें अन्यथा गलत
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
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