检查字符的频率是否在Python中的Recaman系列中

假设我们有一个小写的字符串s。我们必须检查以任何可能的方式重新排列后，s中字母的出现是否生成了Recaman序列（忽略第一个术语）。

Recaman的序列如下-

$$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}$$

Recaman序列的某些项目是[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)。因此，频率构成了Recaman序列的前几个项[1、3、6、2]。

示例

让我们看下面的实现以更好地理解-

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