Go to Qiita Advent Calendar 2024 Top
LoginSignup
1
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@hibit(hibit at)

位相空間の数え上げをbit演算で行う

Posted at

位相空間の定義

　位相空間（≒開集合）は以下のように定義される。

$$

  1. \varnothing,X \subseteq \mathcal{O} \\
  2. \forall O_1,O_2 \in A : O_1 \cap O_2 \in \mathcal{O} \\
  3. \forall [O_\lambda]_{\lambda \in \Lambda} : \bigcup _ {\lambda \in \Lambda} O _\lambda \in \mathcal{O}
    $$

　要は、集合の集合（ややこしいので集合族と呼ぶ）において、お互いの和集合または積集合がまた同じ集合族に属するようなもののことである。

　例えば$a,b,c$が全要素である場合、

$$
(\varnothing),(b),(a,b),(b,c),(a,b,c)
$$

　は位相空間である（※$\varnothing$は空集合）。$(a,b)$と$(b,c)$の積集合$(a)$は同じグループに属するからである。他の任意の集合の組み合わせについても同様である。
　
　ちなみに大学数学の書籍にしては珍しく、「はじめよう　位相空間」には位相空間の素朴な数え上げの例題（と、嫌々ながらも解答が）がある。

image.png

　いかにもbit演算で行えそうな計算である。プログラムしてみる。

考え方

　$N=3$ の時を考える。

　ありえる集合としては、
$$(\varnothing),(a),(b),(c),(a,b),(b,c),(c,a),(a,b,c)$$
　の8通りである。これは$2^3 = 8$通りなので 3bit で表現できる。列挙すると以下の通り。

0 = 000 ()
1 = 001 (a)
2 = 010 (b)
3 = 011 (a,b)
4 = 100 (c)
5 = 101 (a,c)
6 = 110 (b,c)
7 = 111 (a,b,c)

　では、これらの集合を含むか含まないかは、それを更にbit演算すればいい。$2^{2^3} = 65536$ 通りである。上のグループ $0\thicksim7$ を便宜的に $G0\thicksim G7$ と名付ける。

0 = 00000000 ()
1 = 00000001 (G0)
2 = 00000010 (G1)
3 = 00000011 (G0,G1)
.
.
.
65531 = 11111100 (G2,G3,G4,G5,G6,G7)
65532 = 11111101 (G0,G2,G3,G4,G5,G6,G7)
65534 = 11111110 (G1,G2,G3,G4,G5,G6,G7)
65535 = 11111111 (G0,G1,G2,G3,G4,G5,G6,G7)

　さて、それぞれのグループの積集合・和集合はそのままお互いの数のand演算とor演算で実装できる。$(a,b)$と$(b,c)$の積集合は$(b)$,和集合は$(a,b,c)$であるが、これはbit演算でいうと3&6=2と3|6=7に対応する。

コード

　コードに落とし込む。

条件1

　これは簡単だ。状態数のbitの左端と右端が立っているかを調べればよい。

def O1(i):
    if i&1 == 0:#∅を含むか
        return False
    bitlim = (1<<3)-1
    if i>>bitlim&1 == 0:#全体集合を含むか
        return False
    return True

条件2

　状態数に含まれるbitをカウントした上で、それぞれの積集合がbitに集合族に含まれるかを調べる。

def O2(i):
    num = 0
    sets = [] #bitを数えておくリスト
    for j in range(1<<3):
        if i>>j&1:
            num += 1
            sets.append(j)
    for j in range(1<<num):
        if j == 0:
            continue
        tmp = 0 #含まれるbitの全和集合
        for k in range(num):
            tmp |= sets[k]
        for k in range(num):
            if j>>k&1:
                tmp &= sets[k] #積集合をとっていく
        if tmp not in sets:
            return False #bitリストに含まれていなかったらアウト
    return True

条件3

　基本的には条件2の演算子を変えただけのものになる。

def O3(i,points):
    num = 0
    sets = []
    for j in range(1<<points):
        if i>>j&1:
            num += 1
            sets.append(j)
    for j in range(1<<num):
        if j == 0:
            continue
        tmp = 0
        for k in range(num):
            if j>>k&1:
                tmp |= sets[k]
        if tmp not in sets:
            return False
    return True

　以上の関数を定義した上で、

def setstext(i):
    chars = 'abc'
    ans = []
    for j in range(1<<3):
        if i>>j&1:
            tmp = []
            for k in range(3):
                if (j>>k)&1:
                    tmp.append(chars[k])
            if len(tmp) == 0:
                tmp.append('∅')
            elif len(tmp) == points:
                tmp = ['S']
            ans.append(tmp)
    return ans

def isOpen(i):
    if not O1(i):
        return 0
    if not O2(i):
        return 0
    if not O3(i):
        return 0
    print(setstext(i))
    return 1

def main():
    count = 0
    max_range = 1<<(1<<3)
    for i in range(max_range):
        count += isOpen(i)
    print(count)

main()

　と実行すれば以下の解答が得られる。

[['∅'], ['S']]
[['∅'], ['a'], ['S']]
[['∅'], ['b'], ['S']]
[['∅'], ['a', 'b'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['S']]
[['∅'], ['c'], ['S']]
[['∅'], ['a', 'b'], ['c'], ['S']]
[['∅'], ['a', 'c'], ['S']]
[['∅'], ['a'], ['a', 'c'], ['S']]
[['∅'], ['b'], ['a', 'c'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['a', 'c'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['a', 'c'], ['S']]
[['∅'], ['c'], ['a', 'c'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['c'], ['a', 'c'], ['S']]
[['∅'], ['b', 'c'], ['S']]
[['∅'], ['a'], ['b', 'c'], ['S']]
[['∅'], ['b'], ['b', 'c'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['b', 'c'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['b', 'c'], ['S']]
[['∅'], ['c'], ['b', 'c'], ['S']]
[['∅'], ['b'], ['c'], ['b', 'c'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['c'], ['b', 'c'], ['S']]
[['∅'], ['c'], ['a', 'c'], ['b', 'c'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['b', 'c'], ['S']]
[['∅'], ['b'], ['c'], ['a', 'c'], ['b', 'c'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['S']]
29

　これは教科書の答えと一致する。

一般化

　せっかくなので一般化する。集合の要素の数をpointsとする。

def O1(i,points):
    if i&1 == 0:#∅を含むか
        return False
    bitlim = (1<<points)-1
    if i>>bitlim&1 == 0:#全体集合を含むか
        return False
    return True

def O2(i,points):
    num = 0
    sets = []
    for j in range(1<<points):
        if i>>j&1:
            num += 1
            sets.append(j)
    for j in range(1<<num):
        if j == 0:
            continue
        tmp = 0
        for k in range(num):
            tmp |= sets[k]
        for k in range(num):
            if j>>k&1:
                tmp &= sets[k]
        if tmp not in sets:
            return False
    return True

def O3(i,points):
    num = 0
    sets = []
    for j in range(1<<points):
        if i>>j&1:
            num += 1
            sets.append(j)
    for j in range(1<<num):
        if j == 0:
            continue
        tmp = 0
        for k in range(num):
            if j>>k&1:
                tmp |= sets[k]
        if tmp not in sets:
            return False
    return True

def setstext(i,points):
    chars = 'abcdefghijklmnopqrstuvxyz' #zまでやったら計算時間で地球が爆発する
    ans = []
    for j in range(1<<points):
        if i>>j&1:
            tmp = []
            for k in range(points):
                if (j>>k)&1:
                    tmp.append(chars[k])
            if len(tmp) == 0:
                tmp.append('∅')
            elif len(tmp) == points:
                tmp = ['S']
            ans.append(tmp)
    return ans

def isOpen(i,points):
    if not O1(i,points):
        return 0
    if not O2(i,points):
        return 0
    if not O3(i,points):
        return 0
    print(setstext(i,points))
    return 1

def main(points):
    count = 0
    max_range = 1<<(1<<points)
    for i in range(max_range):
        count += isOpen(i,points)
    print(count)

points = 4
main(points)

実行結果

points = 1
...
[['∅'], ['S']]
1

points = 2
...
[['∅'], ['S']]
[['∅'], ['a'], ['S']]
[['∅'], ['b'], ['S']]
[['∅'], ['a'], ['b'], ['S']]
4

points = 3
（略）
29

points = 4
...
[['∅'], ['S']]
[['∅'], ['a'], ['S']]
[['∅'], ['b'], ['S']]
[['∅'], ['a', 'b'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['S']]
[['∅'], ['c'], ['S']]
[['∅'], ['a', 'c'], ['S']]
[['∅'], ['a'], ['a', 'c'], ['S']]
[['∅'], ['c'], ['a', 'c'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['S']]
[['∅'], ['b', 'c'], ['S']]
[['∅'], ['b'], ['b', 'c'], ['S']]
[['∅'], ['c'], ['b', 'c'], ['S']]
[['∅'], ['b'], ['c'], ['b', 'c'], ['S']]
[['∅'], ['a', 'b', 'c'], ['S']]
[['∅'], ['a'], ['a', 'b', 'c'], ['S']]
[['∅'], ['b'], ['a', 'b', 'c'], ['S']]
[['∅'], ['a', 'b'], ['a', 'b', 'c'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['a', 'b', 'c'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['a', 'b', 'c'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['a', 'b', 'c'], ['S']]
[['∅'], ['c'], ['a', 'b', 'c'], ['S']]
[['∅'], ['a', 'b'], ['c'], ['a', 'b', 'c'], ['S']]
[['∅'], ['a', 'c'], ['a', 'b', 'c'], ['S']]
[['∅'], ['a'], ['a', 'c'], ['a', 'b', 'c'], ['S']]
[['∅'], ['b'], ['a', 'c'], ['a', 'b', 'c'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['a', 'c'], ['a', 'b', 'c'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['a', 'c'], ['a', 'b', 'c'], ['S']]
[['∅'], ['c'], ['a', 'c'], ['a', 'b', 'c'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['a', 'b', 'c'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['c'], ['a', 'c'], ['a', 'b', 'c'], ['S']]
[['∅'], ['b', 'c'], ['a', 'b', 'c'], ['S']]
[['∅'], ['a'], ['b', 'c'], ['a', 'b', 'c'], ['S']]
[['∅'], ['b'], ['b', 'c'], ['a', 'b', 'c'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['b', 'c'], ['a', 'b', 'c'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['b', 'c'], ['a', 'b', 'c'], ['S']]
[['∅'], ['c'], ['b', 'c'], ['a', 'b', 'c'], ['S']]
[['∅'], ['b'], ['c'], ['b', 'c'], ['a', 'b', 'c'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['c'], ['b', 'c'], ['a', 'b', 'c'], ['S']]
[['∅'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['S']]
[['∅'], ['b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['S']]
[['∅'], ['d'], ['S']]
[['∅'], ['a', 'b', 'c'], ['d'], ['S']]
[['∅'], ['a', 'd'], ['S']]
[['∅'], ['a'], ['a', 'd'], ['S']]
[['∅'], ['b', 'c'], ['a', 'd'], ['S']]
[['∅'], ['a'], ['a', 'b', 'c'], ['a', 'd'], ['S']]
[['∅'], ['a'], ['b', 'c'], ['a', 'b', 'c'], ['a', 'd'], ['S']]
[['∅'], ['d'], ['a', 'd'], ['S']]
[['∅'], ['a'], ['d'], ['a', 'd'], ['S']]
[['∅'], ['a'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['S']]
[['∅'], ['b', 'd'], ['S']]
[['∅'], ['b'], ['b', 'd'], ['S']]
[['∅'], ['a', 'c'], ['b', 'd'], ['S']]
[['∅'], ['b'], ['a', 'b', 'c'], ['b', 'd'], ['S']]
[['∅'], ['b'], ['a', 'c'], ['a', 'b', 'c'], ['b', 'd'], ['S']]
[['∅'], ['d'], ['b', 'd'], ['S']]
[['∅'], ['b'], ['d'], ['b', 'd'], ['S']]
[['∅'], ['b'], ['a', 'b', 'c'], ['d'], ['b', 'd'], ['S']]
[['∅'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['a', 'b', 'd'], ['S']]
[['∅'], ['b'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a', 'b'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['a', 'b', 'd'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['a', 'b', 'd'], ['S']]
[['∅'], ['c'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['a', 'c'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['a', 'b', 'd'], ['S']]
[['∅'], ['b'], ['b', 'c'], ['a', 'b', 'd'], ['S']]
[['∅'], ['b'], ['c'], ['b', 'c'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'b', 'd'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a', 'b'], ['c'], ['a', 'b', 'c'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['a', 'c'], ['a', 'b', 'c'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['a', 'c'], ['a', 'b', 'c'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['c'], ['a', 'c'], ['a', 'b', 'c'], ['a', 'b', 'd'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['b', 'c'], ['a', 'b', 'c'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['b', 'c'], ['a', 'b', 'c'], ['a', 'b', 'd'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['c'], ['b', 'c'], ['a', 'b', 'c'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['a', 'b', 'd'], ['S']]
[['∅'], ['d'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a', 'b'], ['d'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a', 'b'], ['a', 'b', 'c'], ['d'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['a', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['b'], ['a', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['a', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['a', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['b'], ['b', 'c'], ['a', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['b', 'c'], ['a', 'b', 'c'], ['a', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['d'], ['a', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['d'], ['a', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['d'], ['a', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['b', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['b', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['b'], ['b', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['b', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['b', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['a', 'c'], ['b', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['a', 'b', 'c'], ['b', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['a', 'b', 'c'], ['b', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['a', 'c'], ['a', 'b', 'c'], ['b', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['d'], ['b', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['b'], ['d'], ['b', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['d'], ['b', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['a', 'b', 'c'], ['d'], ['b', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['b'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['S']]
[['∅'], ['c', 'd'], ['S']]
[['∅'], ['a', 'b'], ['c', 'd'], ['S']]
[['∅'], ['c'], ['c', 'd'], ['S']]
[['∅'], ['c'], ['a', 'b', 'c'], ['c', 'd'], ['S']]
[['∅'], ['a', 'b'], ['c'], ['a', 'b', 'c'], ['c', 'd'], ['S']]
[['∅'], ['d'], ['c', 'd'], ['S']]
[['∅'], ['c'], ['d'], ['c', 'd'], ['S']]
[['∅'], ['c'], ['a', 'b', 'c'], ['d'], ['c', 'd'], ['S']]
[['∅'], ['d'], ['a', 'b', 'd'], ['c', 'd'], ['S']]
[['∅'], ['a', 'b'], ['d'], ['a', 'b', 'd'], ['c', 'd'], ['S']]
[['∅'], ['c'], ['d'], ['a', 'b', 'd'], ['c', 'd'], ['S']]
[['∅'], ['a', 'b'], ['c'], ['a', 'b', 'c'], ['d'], ['a', 'b', 'd'], ['c', 'd'], ['S']]
[['∅'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['a', 'c', 'd'], ['S']]
[['∅'], ['b'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['a', 'c', 'd'], ['S']]
[['∅'], ['c'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a', 'c'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['a', 'c'], ['a', 'c', 'd'], ['S']]
[['∅'], ['c'], ['a', 'c'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['a', 'c', 'd'], ['S']]
[['∅'], ['c'], ['b', 'c'], ['a', 'c', 'd'], ['S']]
[['∅'], ['b'], ['c'], ['b', 'c'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a', 'c'], ['a', 'b', 'c'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['a', 'c'], ['a', 'b', 'c'], ['a', 'c', 'd'], ['S']]
[['∅'], ['b'], ['a', 'c'], ['a', 'b', 'c'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['a', 'c'], ['a', 'b', 'c'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['a', 'c'], ['a', 'b', 'c'], ['a', 'c', 'd'], ['S']]
[['∅'], ['c'], ['a', 'c'], ['a', 'b', 'c'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['a', 'b', 'c'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['c'], ['a', 'c'], ['a', 'b', 'c'], ['a', 'c', 'd'], ['S']]
[['∅'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['a', 'c', 'd'], ['S']]
[['∅'], ['b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['a', 'c', 'd'], ['S']]
[['∅'], ['d'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a', 'c'], ['d'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['a', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['c'], ['a', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['a', 'c'], ['a', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['a', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['c'], ['b', 'c'], ['a', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['a', 'c'], ['a', 'b', 'c'], ['a', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['a', 'b', 'c'], ['a', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['a', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['d'], ['a', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['d'], ['a', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['a', 'c'], ['d'], ['a', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['a', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['d'], ['b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['b'], ['d'], ['b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a', 'c'], ['d'], ['b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['b'], ['a', 'c'], ['a', 'b', 'c'], ['d'], ['b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a', 'd'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['a', 'd'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['b'], ['a', 'd'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['a', 'd'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['a', 'd'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['c'], ['a', 'd'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['a', 'c'], ['a', 'd'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['a', 'd'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['b'], ['c'], ['b', 'c'], ['a', 'd'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['a', 'c'], ['a', 'b', 'c'], ['a', 'd'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['a', 'c'], ['a', 'b', 'c'], ['a', 'd'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['c'], ['a', 'c'], ['a', 'b', 'c'], ['a', 'd'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['a', 'd'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['d'], ['a', 'd'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['d'], ['a', 'd'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['d'], ['a', 'd'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['a', 'c'], ['d'], ['a', 'd'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['a', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['b'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['a', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['a', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['c', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['c', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['c', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['c'], ['c', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['c'], ['a', 'c'], ['c', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['c', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['c'], ['a', 'c'], ['a', 'b', 'c'], ['c', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['a', 'b', 'c'], ['c', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['c'], ['a', 'c'], ['a', 'b', 'c'], ['c', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['d'], ['c', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['c'], ['d'], ['c', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['c'], ['a', 'c'], ['d'], ['c', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['c'], ['a', 'c'], ['a', 'b', 'c'], ['d'], ['c', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['d'], ['a', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['d'], ['a', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['c'], ['d'], ['a', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['d'], ['a', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['d'], ['a', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['d'], ['a', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['d'], ['a', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['c'], ['d'], ['a', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['d'], ['a', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['a'], ['a', 'b'], ['c'], ['a', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['S']]
[['∅'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['a', 'c'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b', 'c'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['b', 'c'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['b', 'c'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['c'], ['b', 'c'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b', 'c'], ['a', 'b', 'c'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['b', 'c'], ['a', 'b', 'c'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['b', 'c'], ['a', 'b', 'c'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['b', 'c'], ['a', 'b', 'c'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['b', 'c'], ['a', 'b', 'c'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['b', 'c'], ['a', 'b', 'c'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['c'], ['b', 'c'], ['a', 'b', 'c'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['c'], ['b', 'c'], ['a', 'b', 'c'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['b', 'c', 'd'], ['S']]
[['∅'], ['d'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b', 'c'], ['d'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['b', 'c', 'd'], ['S']]
[['∅'], ['d'], ['a', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['d'], ['a', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b', 'c'], ['d'], ['a', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['a', 'c'], ['b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['b', 'c'], ['b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['c'], ['b', 'c'], ['b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['b', 'c'], ['a', 'b', 'c'], ['b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['c'], ['b', 'c'], ['a', 'b', 'c'], ['b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['d'], ['b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['d'], ['b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['b', 'c'], ['d'], ['b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b', 'd'], ['a', 'b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['b', 'd'], ['a', 'b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['b', 'd'], ['a', 'b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['b', 'd'], ['a', 'b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['b', 'd'], ['a', 'b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['b', 'd'], ['a', 'b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['b', 'd'], ['a', 'b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['b', 'c'], ['b', 'd'], ['a', 'b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['c'], ['b', 'c'], ['b', 'd'], ['a', 'b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['b', 'c'], ['a', 'b', 'c'], ['b', 'd'], ['a', 'b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['b', 'c'], ['a', 'b', 'c'], ['b', 'd'], ['a', 'b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['c'], ['b', 'c'], ['a', 'b', 'c'], ['b', 'd'], ['a', 'b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['b', 'd'], ['a', 'b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['d'], ['b', 'd'], ['a', 'b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['d'], ['b', 'd'], ['a', 'b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['d'], ['b', 'd'], ['a', 'b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['b', 'c'], ['d'], ['b', 'd'], ['a', 'b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['b', 'd'], ['a', 'b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['b', 'c'], ['c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['c'], ['b', 'c'], ['c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['b', 'c'], ['a', 'b', 'c'], ['c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['c'], ['b', 'c'], ['a', 'b', 'c'], ['c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['c'], ['b', 'c'], ['a', 'b', 'c'], ['c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['d'], ['c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['d'], ['c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['b', 'c'], ['d'], ['c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['d'], ['b', 'd'], ['c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['d'], ['b', 'd'], ['c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['d'], ['b', 'd'], ['c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['c'], ['b', 'c'], ['d'], ['b', 'd'], ['c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['b', 'd'], ['c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['d'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['d'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['d'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['d'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['c'], ['b', 'c'], ['d'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['a', 'b'], ['c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['a', 'c'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['b', 'c'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['c'], ['b', 'c'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['d'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['d'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['a', 'c'], ['d'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['b', 'c'], ['d'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['d'], ['a', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['d'], ['a', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['d'], ['a', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['d'], ['a', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['b', 'c'], ['d'], ['a', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['d'], ['b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['d'], ['b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['d'], ['b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['a', 'c'], ['d'], ['b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['c'], ['b', 'c'], ['d'], ['b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['c'], ['a', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['b'], ['c'], ['b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
[['∅'], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c'], ['d'], ['a', 'd'], ['b', 'd'], ['a', 'b', 'd'], ['c', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['S']]
355

　n=4ですごい数である。この答えがあっているかについては、奈良教育大学学術リポジトリの紀要論文（40年近く前！）でも同様の計算が行われているが、合ってそうである。

　ちなみにnを5以上にするとすごい時間がかかる。計算量オーダーを見積もったところ、

$$
O(2^{2^n+2n})
$$

　とすごいことになったので、アルゴリズムを洗練させないとこれ以上は無理だと思われる。

1
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?