12セグメントで文字を作る

ホームへ

7セグメントディスプレイってありますよね。←こういうやつです。デジタル数字と言うと大抵これのことを指し、横線3本・縦線4本からなる7つのセグメントを点けたり消したりすることで数字（文字）を表示することができます。ただ7セグメントというのはなかなか小さくて、表現できる形には限りがあります。論理的にも128 (2⁷) 通りしかなく、ラテン文字を例に取っても K と X を H と区別して表示するのは無理ですね。これを解消するためにセグメントを増やしたディスプレイにはいくつかの種類があるようです。

ただ、斜線を使うと、表せるものが増えはする一方で雰囲気が結構変わってしまうんですよね。斜線を含むnセグメントディスプレイの例として、ロシアの郵便番号の表記を載せました。ロシアでは、郵便番号は図下部のような数字を図上部のように与えられる記入欄に書き込むようです。これらの字体は、7セグメントディスプレイに斜線を2本付け足した「9セグメント」に基づいていると言えます。

そこで、斜線を使わずに表せる図形を増やすために、田の字型に12本のセグメントを配置したディスプレイを考えます。セグメントが5本増えると32倍の図形が区別できるようになるので、かなり表現力が広がりそうです。この「12セグメントディスプレイ」では、何種類の図形が区別できるのでしょうか？

ということで、次の条件を満たす図形の数を数えてみましょう。

12セグメントのディスプレイに表示される。以降、次の図のようにセグメントに番号を付ける。
横幅・縦幅ともに0または2のもの。ただし、横幅と縦幅の少なくとも一方は2とする。
連結なもの。

条件1は良いでしょう。条件2は、幅1のものは、適当に延長して幅2のものと同一視してしまうということです。例えば {3, 6, 7} と {8, 11, 12} は {3, 8, 11, 12} と同じと見ます。特定の方向に伸縮させれば一致する形ですから、これも良いでしょう。後半は、縦横ともに幅0の「図形」を除くためです。条件3については、二つの理由があります。一つは、非連結なもの（{1, 3, 8, 9, 10, 12} など）は一文字として認識しにくいためです。もちろん自然の文字体系にはギリシャ文字の「Ξ」（ξ の大文字）やヘブライ文字の「ה」、片仮名の「ハ」のような例があるので、理由としては少し弱いですね。もう一つの理由は、それらを許容する場合、条件2から縦幅と横幅のどちらかが1である 2×2×2⁷ = 2⁹ 個以下（7セグメントで表せる図形を縦向き2箇所・横向き2箇所に配置することを考える）の図形が除かれるとはいえ、論理的に可能な 2¹² 個のうち半数以上の図形が許容されてしまうためです。そうなるとわざわざ調べるには面白みに欠けますね。そこで、今回は連結という制約を課してみることにしましょう。

さて、条件2について考えると、縦幅が0のものは、横幅が2の3つ（ {1, 2} , {6, 7} , {11, 12} ）しかありません。これらは同一視してしまいましょう。横幅が0のものについても同様です。すると、幅の一方が0の図形は2種類のみということになります。では、幅が縦横ともに2であるものを考えていきましょう。条件3の連結性制約を合わせて考えると、横幅を2にするためには

左側の横線： {1, 6, 11}
右側の横線： {2, 7, 12}

からそれぞれ少なくとも1つ以上取る必要があり、縦幅を2にするためには

上側の縦線： {3, 4, 5}
下側の縦線： {8, 9, 10}

からそれぞれ少なくとも1つ以上取る必要があります（例えば {1, 6, 12} も縦幅2ですが、連結ではありません。連結であるためには {1, 3, 6, 9, 12} のように縦線を足してやる必要があります）。従って、条件を満たす図形は (2³ - 1)⁴ = 2401 から、最大で2401通りあるみたいですね。

さて、これら2401個の図形について考えていくのですが、条件3にある通り連結でないものを除外したいところです。ただ、実際にプログラムを走らせる以外の方法がどうも思いつきません。仕方がないのでコンピュータに投げましょう。連結かどうかは、セグメントの隣接関係が分かれば判定できます。隣接関係は次のグラフのように整理できますね。頂点がセグメント、辺がセグメントの隣接関係です。（セグメント上に描かれる図形はこのグラフの部分グラフと見做せます。特にセグメント間の隣接関係はディスプレイ上の配置に従うものなので、誘導部分グラフであると言えます。）

あとはプログラムをぶん回すだけです。

ソースコード

from itertools import chain, combinations, product

# セグメントとその隣接関係
vertices = [[1, 6, 11], [2, 7, 12], [3, 4, 5], [8, 9, 10]]
edges = {
    1: [2, 3, 4], 
    2: [1, 4, 5], 
    3: [1, 6, 8], 
    4: [1, 2, 6, 7, 9], 
    5: [2, 7, 10], 
    6: [3, 4, 7, 8, 9], 
    7: [4, 5, 6, 9, 10], 
    8: [3, 6, 11], 
    9: [4, 6, 7, 11, 12], 
    10: [5, 7, 12], 
    11: [8, 9, 12], 
    12: [9, 10, 11], 
}

# 空集合でない冪集合を得る関数
def powerset(l):
    return chain.from_iterable(combinations(l, r) for r in range(1, len(l)+1))

# 誘導部分グラフが連結であるかを調べる関数
def is_connected(vertices, edges):
    # ある頂点 vertex から先を探索する関数
    def search(vertex, visited):
        visited.add(vertex)

        for paired in [paired for paired in edges[vertex] if paired in vertices]:
            if paired not in visited:
                visited = search(paired, visited)

        return visited

    # 適当な頂点から探索を行い、全ての頂点を訪問できれば連結
    component = search(vertices[0], set())
    connected = set(vertices) == component

    return connected

# 計算
counter = [0, 0]  # [非連結の個数, 連結の個数]

with open("data.txt", "w") as o:
    powersets = map(powerset, vertices)

    for i in product(*powersets):
        subset_vertices = list(chain.from_iterable(i))
        connected = is_connected(subset_vertices, edges)

        if connected:
            print(sorted(subset_vertices), file=o)
        
        counter[connected] += 1

print(f"Connected: {counter[1]}, Disconnected: {counter[0]}")

Connected: 1493, Disconnected: 908

ということで、1493個の連結な図形が得られました。具体的な図形のリストは .txt ファイルとして書き出しています。これらは幅が縦横ともに2のものです。いずれかの幅が0であるもの2種類を足し合わせて1495個の図形が12セグメントのディスプレイで表示可能な「文字」だということになりました。思ったよりありますね。

余談　先のプログラムでは、冒頭で二つの変数vertices, edgesを定義しています。verticesにはセグメントの集合の適切な分割（前述の通り）を与えています。またedgesにはディスプレイをグラフとして表したものの隣接リストを与えています。これらを目的のkセグメントディスプレイに合わせて設定すれば、（十分に小さいものなら）どのようなディスプレイにも対応できるわけです。ということで m ≤ 4, n ≤ 4 の範囲で調べてみました。ついでに、verticesとedgesを自動で計算してくれる関数graphgenを作って利用したので載せておきます。

graphgenのコード

def graphgen(m, n):
    # セグメントディスプレイを生成
    segments = []
    k = 1

    for i in range(n+n+1):
        width = m if i % 2 == 0 else m+1
        segments.append(list(range(k, k + width)))
        k += width

    # それぞれのブロックから少なくとも1つ以上選ぶべきセグメント集合の分割を生成
    vertices = []
    for j in range(m):
        vertices.append([segments[i][j] for i in range(0, len(segments), 2)])
    for i in range(1, len(segments), 2):
        vertices.append(segments[i])

    # セグメントの隣接関係を生成
    edges = {}

    def append_if_exists(ll, i, j, target):
        if 0 <= i and i < len(ll) and 0 <= j and j < len(ll[i]):
            target.append(ll[i][j])

    for i in range(len(segments)):
        row = segments[i]
        for j in range(len(segments[i])):
            paired = []

            if i % 2 == 0:
                # 左端の左: segments[i] の1つ前
                append_if_exists(segments, i, j-1, paired)

                # 右端の右: segments[i] の1つ後
                append_if_exists(segments, i, j+1, paired)

                # 左端の上: segments の1つ前のリストの同じ位置
                append_if_exists(segments, i-1, j, paired)

                # 右端の上: segments の1つ前のリストの1つ後
                append_if_exists(segments, i-1, j+1, paired)

                # 左端の下: segments の1つ後のリストの同じ位置
                append_if_exists(segments, i+1, j, paired)

                # 右端の下: segments の1つ後のリストの1つ後
                append_if_exists(segments, i+1, j+1, paired)
            else:
                # 上端の左: segments の1つ前のリストの1つ前
                append_if_exists(segments, i-1, j-1, paired)

                # 上端の右: segments の1つ前のリストの同じ位置
                append_if_exists(segments, i-1, j, paired)

                # 上端の上: segments の2つ前のリストの同じ位置
                append_if_exists(segments, i-2, j, paired)

                # 下端の左: segments の1つ後のリストの1つ前
                append_if_exists(segments, i+1, j-1, paired)

                # 下端の右: segments の1つ後のリストの同じ位置
                append_if_exists(segments, i+1, j, paired)

                # 下端の上: segments の2つ後のリストの同じ位置
                append_if_exists(segments, i+2, j, paired)

            edges[row[j]] = paired

    return [vertices, edges]

上段：表示可能な「文字」（幅が 0 または m,n の空でない連結な図形）の種類
中段：分割に基づく「文字」の種類の上限 (2^m+1 - 1)ⁿ(2ⁿ⁺¹ - 1)^m
下段：論理的な図形の種類 2^s (セグメントの数 s = (m+1)n + m(n+1))

m \ n	1	2	3	4
1	\(9\) \(9\) \(16\)	\(53\) \(63\) \(128\)	\(279\) \(405\) \(1024\)	\(1431\) \(2511\) \(8192\)
2	\(53\) \(63\) \(128\)	\(1493\) \(2401\) \(4096\)	\(34911\) \(77175\) \(131072\)	\(776689\) \(2307361\) \(4194304\)
3	\(279\) \(405\) \(1024\)	\(34911\) \(77175\) \(131072\)	\(3417353\) \(11390625\) \(16777216\)	\(311995809\) \(1508169375\) \(2147483648\)
4	\(1431\) \(2511\) \(8192\)	\(776689\) \(2307361\) \(4194304\)	\(311995809\) \(1508169375\) \(2147483648\)	\(?\) \(852891037441\) \(1099511627776\)

(m, n) = (3, 4) の時点で（multiprocessingによる数倍の高速化をした上で）計算に90分以上掛かったので、 (m, n) = (4, 4) のときの計算は諦めました。真面目に求めていませんが、先のプログラムでは (2^m+1 - 1)ⁿ(2ⁿ⁺¹ - 1)^m 回のループを回していて、かつその中で頂点と辺の数が mn のオーダーのグラフ（頂点はセグメントの数なので (m+1)n + m(n+1) 個、辺はセグメントは最大6つとしか隣り合えないので高々その6倍）に対して深さ優先探索をしているので、計算量は下から Ω(2^mnmn) と押さえられます（深さ優先探索の計算量についての参考）。でっか。改善できないのかな……

おまけ　12セグメントディスプレイに表示できる「文字」を一覧にしてみました。