Pythonで各文字が直後の文字より辞書順に大きくなる文字列を生成する方法

問題の概要

数値 n が与えられたとき、小文字のみで構成される長さ n+1 の文字列を作成することを考えます。条件は、任意の位置にある文字が、その直後の文字よりも辞書式順序(lexicographic order)で大きくなることです。

たとえば、入力が 15 の場合、出力は次のようになります。

ponmlkjihgfedcba

この文字列では、先頭の「p」から末尾の「a」に向かって文字が辞書順に小さくなっていくため、すべての隣接する文字のペアで条件が満たされています。

解決のためのアプローチ

鍵となるのは、逆順に並べたアルファベット「zyxwvutsrqponmlkjihgfedcba」です。この文字列はもともと、どの文字も直後の文字より大きいため、必要な長さに応じて一部を切り出すだけで条件を満たす文字列が得られます。具体的には、以下の手順で処理を行います。

1. 空の文字列 temp_str を用意します。
2. extra = n % 26 を計算します(n を 26 で割った余り)。
3. extra が 1 以上の場合、逆順アルファベットのインデックス 26 − (extra + 1) から 25 までの文字、つまり末尾の extra + 1 文字を temp_str に連結します。
4. count = n // 26(整数除算)を計算します。
5. count 回のループで、逆順アルファベット全 26 文字を temp_str に連結します。
6. temp_str を結果として返します。

実装例

理解を深めるために、Python での実装を見てみましょう。

def show_string(n, str):
    temp_str = ""
    extra = n % 26
    if (extra >= 1):
        for i in range(26 - (extra + 1), 26):
            temp_str += str[i]
    count = n // 26
    for i in range(1, count + 1):
        for j in range(26):
            temp_str += str[j]
    return temp_str

n = 15
str = "zyxwvutsrqponmlkjihgfedcba"
print(show_string(n, str))

入力

15

出力

ponmlkjihgfedcba

処理の流れの解説

n = 15 の場合を具体的に追ってみます。まず extra = 15 % 26 = 15 となるため、逆順アルファベットのインデックス 10 〜 25 にあたる 16 文字(p から a まで)が切り出されて temp_str に追加されます。次に count = 15 // 26 = 0 となるため、全 26 文字を繰り返し追加するループは一度も実行されません。その結果として「ponmlkjihgfedcba」が出力され、すべての隣接ペアで左側の文字が右側の文字より大きいという条件を満たしていることが確認できます。