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

数値nと別の値kがあるとします。ここで、「0」、「1」、および「2」のみを含み、文字が連続して繰り返されない文字列について考えてみましょう。長さnのそのような文字列を選択し、辞書式順序で最小のk番目の文字列を見つける必要があります。 k番目の文字列がない場合は、空の文字列を返します。

したがって、入力がn =4 k =2の場合、出力は「0120」になります。

これを解決するには、次の手順に従います。

• メソッドsolve（）を定義します。これには、s、k、およびlastが必要です
• sが0と同じ場合、
  • 空白の文字列を返す
• 「012」の各文字cについて、
  • cがlastと同じ場合、
    • 次の反復に進む
  • k <2 ^（s-1）の場合、
    • return c +solve（s-1、k、c）
  • k：=k-2 ^（s-1）
• 空白の文字列を返す
• メインメソッド呼び出しからsolve（n、k、Null）

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

サンプルコード

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