Pythonで長さnのすべての上下反転数（Upside-Down Number）を生成する方法

ある値 n が与えられたとき、その桁数（長さ）を持つすべての「上下反転数（Upside-Down Number）」を求めることを考えます。上下反転数とは、180度回転させても同じように見える数字のことです。

たとえば、入力が n = 2 の場合、出力は ['11', '69', '88', '96'] となります。

上下反転数の仕組み

180度回転しても成立する数字の組み合わせには、次のようなものがあります。

• 0 → 0（そのまま）

• 1 → 1（そのまま）

• 8 → 8（そのまま）

• 6 ↔ 9（互いに入れ替わる）

これら以外の数字（2, 3, 4, 5, 7）は回転すると別の数字や無効な形になってしまうため使用できません。また、先頭に0を置くことはできないため、最も外側のペアでは「00」の組み合わせを除外する必要がある点にも注意しましょう。

解決のためのアプローチ

この問題は、数字列の中央から外側へ向かって対称的に構築していく再帰的な手法で解決できます。手順は以下の通りです。

• 引数 x を受け取る関数 middle() を定義します。

• x が 0 の場合は、空文字列1つだけを含むリストを返します。

• x が 1 の場合は、要素「0」「1」「8」からなる新しいリストを返します。

• ret := 新しい空のリスト

• mid := middle(x − 2) を呼び出します。

• mid 内の各要素 m に対して、次の処理を行います。

  • x が n と等しくない場合（＝最外側のペアではない場合）、ret の末尾に「0 + m + 0」を追加します。

  • ret の末尾に「1 + m + 1」を追加します。

  • ret の末尾に「6 + m + 9」を追加します。

  • ret の末尾に「8 + m + 8」を追加します。

  • ret の末尾に「9 + m + 6」を追加します。

• ret を返します。

• メイン処理では、次のようにします。

  • n が 0 の場合は、空のリストを返します。

  • それ以外の場合は、middle(n) の結果をソートしたリストを返します。

実装例

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

class Solution:
   def solve(self, n):
      if not n:
         return []
      def middle(x=n):
         if not x:
            return [""]
         if x == 1:
            return list("018")
         ret = []
         mid = middle(x - 2)
         for m in mid:
            if x != n:
               ret.append("0" + m + "0")
            ret.append("1" + m + "1")
            ret.append("6" + m + "9")
            ret.append("8" + m + "8")
            ret.append("9" + m + "6")
         return ret
      return sorted(middle())
ob = Solution()
print(ob.solve(2))

入力

2

出力

['11', '69', '88', '96']