HTR Subsets U2

htr_qt3.py

#   0---1
#  /|  /|
# 3---2 |
# | 4-|-5
# |/  |/
# 7---6

import itertools
import random

def move(p, m):
    if False: pass
    elif m=="U":  return (p[3], p[0], p[1], p[2], p[4], p[5], p[6], p[7], 1-p[8])
    elif m=="U2": return (p[2], p[3], p[0], p[1], p[4], p[5], p[6], p[7], p[8])
    elif m=="U'": return (p[1], p[2], p[3], p[0], p[4], p[5], p[6], p[7], 1-p[8])
    elif m=="D":  return (p[0], p[1], p[2], p[3], p[5], p[6], p[7], p[4], 1-p[8])
    elif m=="D2": return (p[0], p[1], p[2], p[3], p[6], p[7], p[4], p[5], p[8])
    elif m=="D'": return (p[0], p[1], p[2], p[3], p[7], p[4], p[5], p[6], 1-p[8])
    elif m=="R2": return (p[0], p[6], p[5], p[3], p[4], p[2], p[1], p[7], p[8])
    elif m=="F2": return (p[0], p[1], p[7], p[6], p[4], p[5], p[3], p[2], p[8])
    elif m=="L2": return (p[7], p[1], p[2], p[4], p[3], p[5], p[6], p[0], p[8])
    elif m=="B2": return (p[5], p[4], p[2], p[3], p[1], p[0], p[6], p[7], p[8])
    else: raise("error")

P = []
for p in itertools.permutations([0, 0, 1, 1, 4, 4, 5, 5]):
    P += [p+(0,)]
    P += [p+(1,)]
P = sorted(list(set(P)))

# 側面の180度回転とU/Dの同時回しで一致するかどうかでグループ化。
G = []
U = [False]*len(P)
for i in range(len(P)):
    if not U[i]:
        p = P[i]
        g = set()
        for _ in range(1000):
            g.add(p)
            U[P.index(p)] = True
            if random.randint(0, 1)==0:
                p = move(move(p, "U"), "D'")
            else:
                p = move(p, ["R2", "F2", "L2", "B2"][random.randint(0, 3)])
        G += [sorted(g)]
G.sort()
#for g in G:
#    print(len(g), g)
#print(len(G))
assert len(G)==136

# グループをさらにグループ化し、グループ内のグループのU系で遷移可能な集合が同一になるように分ける。
# 完成状態を含むグループを0番目に。
G2 = [[], []]
for i in range(len(G)):
    if (0, 1, 0, 1, 4, 5, 4, 5, 0) in G[i] or (0, 1, 5, 4, 1, 0, 4, 5, 0) in G[i]:
        G2[0] += [i]
    else:
        G2[1] += [i]

def getTo(g, moves):
    t = set()
    for x in G[g]:
        for m in moves:
            y = move(x, m)
            for i in range(len(G)):
                if y in G[i]:
                    z = i
            for i in range(len(G2)):
                if z in G2[i]:
                    t.add(i)
    return sorted(list(t))

while True:
    up = False
    for g2 in range(len(G2)):
        t0 = (getTo(G2[g2][0], ["U", "U'"]), getTo(G2[g2][0], ["U2"]))
        x = []
        y = []
        for g in G2[g2]:
            if (getTo(g, ["U", "U'"]), getTo(g, ["U2"]))==t0:
                x += [g]
            else:
                y += [g]
        G2[g2] = x
        if y!=[]:
            G2 += [y]
            up = True
    if not up:
        break

NISS = [set() for _ in range(len(G2))]
for p1 in itertools.permutations(range(8)):
    p2 = tuple(p1.index(i) for i in range(8))
    par = 0
    for i in range(8):
        for j in range(i):
            if p1[j]>p1[i]:
                par ^= 1
    p1 = tuple([x&0b1101 for x in p1]+[par])
    p2 = tuple([x&0b1101 for x in p2]+[par])
    for g2 in range(len(G2)):
        for g in G2[g2]:
            if p1 in G[g]:
                pg1 = g2
            if p2 in G[g]:
                pg2 = g2
    NISS[pg1].add(pg2)

name = [str(i) for i in range(len(G2))]
name[ 0] = "0c0"
name[ 1] = "4a2+"
name[ 2] = "4a1+"
name[ 3] = "4a1-"
name[ 4] = "4a3+b"
name[ 5] = "4b2+"
name[ 6] = "2c3a"
name[ 7] = "2c4+b"
name[ 8] = "4a4+"
name[ 9] = "4b2-"
name[10] = "2c5+"
name[11] = "2c3b"
name[12] = "4b4"
name[13] = "4b3"
name[14] = "4a3+a"
name[15] = "4b5"
name[16] = "4a4-"
name[17] = "4a2-"
name[18] = "0c3"
name[19] = "4a3-"
name[20] = "2c4+a"
name[21] = "2c4-"
name[22] = "2c5-"
name[23] = "0c4"

assert len(set(name))==len(G2)

for g2 in range(len(G2)):
    print(name[g2])
    print("U:", " ".join(name[x] for x in getTo(G2[g2][0], ["U", "U'"])))
    print("U2:", " ".join(name[x] for x in getTo(G2[g2][0], ["U2"])))
    print("NISS:", " ".join(name[x] for x in sorted(list(NISS[g2]))))
    print()

htr_qt3.txt

0c0
U: 4a1+
U2: 0c0
NISS: 0c0

4a2+
U: 4a1- 4b3
U2: 4a2+ 4a2-
NISS: 4a2+ 4a2-

4a1+
U: 0c0 4b2+
U2: 4a1+ 4a1-
NISS: 4a1+ 4a1-

4a1-
U: 4a2+ 4b2+
U2: 4a1+ 4a1-
NISS: 4a1+ 4a1-

4a3+b
U: 4a4+ 4b2- 4b4
U2: 4a3+b 4a3+a 4a3-
NISS: 4b3

4b2+
U: 4a1+ 4a1- 2c3a 2c3b
U2: 4b2+ 4b2-
NISS: 4b2+ 4b2-

2c3a
U: 4b2+ 2c4+b 4b2- 2c4+a
U2: 2c3a 2c3b
NISS: 2c3a 2c3b

2c4+b
U: 2c3a 2c5+ 4b5
U2: 2c4+b 2c4+a 2c4-
NISS: 2c4+b 2c4+a 2c4-

4a4+
U: 4a3+b 4b5
U2: 4a4+ 4a4-
NISS: 4b4

4b2-
U: 4a3+b 2c3a 2c3b 4a3+a
U2: 4b2+ 4b2-
NISS: 4b2+ 4b2-

2c5+
U: 2c4+b 4b4
U2: 2c5+ 2c5-
NISS: 2c5+ 2c5-

2c3b
U: 4b2+ 4b2-
U2: 2c3a
NISS: 2c3a 2c3b

4b4
U: 4a3+b 2c5+ 4a3- 2c5-
U2: 4b4
NISS: 4a4+ 4a4-

4b3
U: 4a2+ 4a2- 2c4+a 2c4-
U2: 4b3
NISS: 4a3+b 4a3+a 4a3-

4a3+a
U: 4b2- 0c4
U2: 4a3+b 4a3-
NISS: 4b3

4b5
U: 2c4+b 4a4+ 4a4- 2c4-
U2: 4b5
NISS: 4b5

4a4-
U: 4b5 0c3
U2: 4a4+ 4a4-
NISS: 4b4

4a2-
U: 4b3 0c3
U2: 4a2+ 4a2-
NISS: 4a2+ 4a2-

0c3
U: 4a4- 4a2-
U2: 0c3
NISS: 0c3

4a3-
U: 4b4 0c4
U2: 4a3+b 4a3+a
NISS: 4b3

2c4+a
U: 2c3a 4b3
U2: 2c4+b 2c4-
NISS: 2c4+b 2c4+a 2c4-

2c4-
U: 4b3 4b5
U2: 2c4+b 2c4+a
NISS: 2c4+b 2c4+a 2c4-

2c5-
U: 4b4
U2: 2c5+
NISS: 2c5+ 2c5-

0c4
U: 4a3+a 4a3-
U2: 0c4
NISS: 0c4