Pythonで文字の出現頻度がレカマン数列と一致するかどうかを判定する方法

小文字のみで構成された文字列 s が与えられたとき、文字列に含まれる各アルファベットの出現回数(頻度)をどのような順序で並べても、レカマン数列(Recaman's Sequence)の初項を除いた項と一致するかどうかを判定する方法を解説します。

レカマン数列とは

レカマン数列は、次の漸化式で定義される有名な整数列です。

• a₀ = 0(n = 0 の場合)
• aₙ = aₙ₋₁ − n(aₙ₋₁ − n が正の数で、かつその値がまだ数列に現れていない場合)
• aₙ = aₙ₋₁ + n(それ以外の場合)

この定義に従うと、レカマン数列の最初のいくつかの項は以下のようになります。

[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] であり、これはレカマン数列の最初のいくつかの項(初項を除く)と完全に一致します。したがって、出力は True になります。

解法のアプローチ

この問題は、次の手順で解くことができます。

• freq := 文字列 s に含まれるすべての文字とその出現回数を保持するマップ(辞書)を作成する
• n := freq のサイズ(= 異なる文字の種類数)とする
• array := レカマン数列の最初の n 項を生成する
• f := 1(判定用フラグ)で初期化する
• freq 内の各文字について以下を繰り返す:
  • is_found := 0 で初期化する
  • j を 1 から n まで順に確認し、freq のキーに対応する頻度が array[j] と一致すれば is_found := 1 としてループを抜ける
  • 最終的に is_found が偽であれば f := 0 として処理を中断する
• すべての頻度が一致していれば(f が 1 のままなら)True を返し、そうでなければ False を返す

Pythonによる実装例

それでは、実際のコードを見てみましょう。

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))

recaman 関数では、「前の項から現在のインデックスを引いた値が正で、かつまだ数列に現れていない場合はその値を採用し、そうでなければ前の項にインデックスを加えた値を採用する」というレカマン数列のルールに従って数列を構築しています。solve 関数は、collections モジュールの defaultdict を使って各文字の出現回数を効率的に集計し、生成したレカマン数列の各項と照合しています。

入力例

"pppuvuuqquuu"

出力例

True

このように、文字ごとの出現頻度を集計してレカマン数列と照合するだけで、与えられた文字列の頻度パターンがレカマン数列を形成するかどうかを簡単に判定できます。