Pythonで辞書式順序k番目に小さい長さnの文字列を求めるプログラム

問題の概要

数値 n と値 k が与えられた場面を考えてみましょう。ここで扱うのは、「0」「1」「2」の3種類の文字だけで構成され、同じ文字が連続して現れないという条件を満たす文字列です。この条件を満たす長さ n の文字列の中から、辞書式順序で k 番目に小さい文字列を求めます。該当する文字列が存在しない場合は、空文字列を返します。

たとえば、入力が n = 4、k = 2 の場合、出力は "0120" となります。

これは、条件を満たす長さ4の文字列を辞書式順序に並べると「0101」「0102」「0120」「0121」…となるため、k = 2 に対応する文字列が "0120" だからです。

解決のためのアプローチ

この問題は、再帰的な手法で効率よく解くことができます。ポイントは、先頭の文字を1つ固定すると、その後に作れる文字列の総数は 2^(s-1) 通りになるという性質です。最初の文字以降は直前の文字と同じ文字を選べないため、各位置で選択肢が2通りに限定されるからです。この性質を利用すれば、すべての候補を列挙してソートする必要がなくなります。

具体的な手順は以下のとおりです。

• s、k、last を引数にとるメソッド solve() を定義します。
• s が 0 の場合、空文字列を返します。
• "012" の各文字 c について、以下の処理を繰り返します。
  • c が last（直前の文字）と同じ場合は、次の反復へ進みます。
  • k < 2^(s-1) であれば、c + solve(s - 1, k, c) を返します。
  • それ以外の場合は、k := k - 2^(s-1) として次の文字へ進みます。
• ループが完了しても見つからなければ、空文字列を返します。
• メイン処理から solve(n, k, None) を呼び出します。

実装例（サンプルコード）

それでは、以下の実装例を見て理解を深めましょう。

class Solution:
    def solve(self, s, k, last=None):
        if s == 0:
            return ""
        for c in "012":
            if c == last:
                continue
            if k < 2 ** (s - 1):
                return c + self.solve(s - 1, k, c)
            k -= 2 ** (s - 1)
        return ""

ob = Solution()
n = 4
k = 2
print(ob.solve(n, k))

入力

4, 2

出力

0120

まとめ

このアルゴリズムでは、各ステップで「現在の文字を選んだ場合に作れる文字列の総数（2^(s-1)）」と k を比較することで、再帰を深く探索せずに目的の文字列を直接特定できます。計算量は再帰の深さに比例する O(n) 程度に抑えられ、すべての文字列を生成して並べ替える指数時間のアプローチと比べて、はるかに高速に動作します。