201227

Python

Dyck path とSelf-avoiding walk の融合(8)

151123(6) 分より多く求めることができた。

from graphillion import GraphSet

def make_stairs(m, n):
    s = 1
    grids = []
    for i in range(m * n + 1, 1, -m):
        for j in range(i - 1):
            a, b, c = s + j, s + j + 1, s + i + j
            grids.append((a, b))
            if j < i - m:
                grids.append((a, c))
        s += i
    return grids

def A(m, n):
    if m== 0 or n == 0: return 1
    universe = make_stairs(m, n)
    GraphSet.set_universe(universe)
    start, goal = m * n + 1, (n + 1) * (m * n + 2) // 2
    paths = GraphSet.paths(start, goal)
    return paths.len()

a = [0, 18, 12, 9, 7, 6]
for m in range(1, 6):
    print([m, [A(m, n) for n in range(a[m])]])

出力結果

[1, [1, 1, 2, 7, 40, 369, 5680, 150707, 6993712, 567670347, 80294818098, 19750798800833, 8447500756620198, 6286515496550185699, 8145835634791919637646, 18387066260739625200447575, 72319765957232441125506763756, 495718308213370458738098777141317]]

[2, [1, 1, 4, 44, 1282, 105022, 25769912, 19275194154, 43766618972372, 300611108229024928, 6247844562000612352002, 393544904039878168133931630]]

[3, [1, 1, 8, 284, 44360, 33970104, 136342264948, 2895975018297704, 323953287601729898128]]

[4, [1, 1, 16, 1872, 1592536, 11455899880, 752600965180800]]

[5, [1, 1, 32, 12384, 57870848, 3912442265360]]

201212

Python


おねえさん問題の３次元版

この記事は
日曜数学 Advent Calendar 2020 (https://adventar.org/calendars/4999)
の12/12 分として書いております。

「nXnXn gird graph の端から端まで、自身と交差することなく、全ての格子点を通る経路」

を数え上げてみた。

私のコードでは3X3X3 gird graph までしか求めることができなかった。

from graphillion import GraphSet

def make_nXnXn_grid_graph(n):
    grids = []
    for x in range(0, n):
        y = x * n * n
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if x < n - 1:
                    grids.append((y + i + (j - 1) * n, y + i + (j - 1) * n + n * n))
                if j < n:
                    grids.append((y + i + (j - 1) * n, y + i + j * n))
        for i in range(1, n * n, n):
            for j in range(1, n):
                grids.append((y + i + j - 1, y + i + j))
    return grids

def A(n):
    universe = make_nXnXn_grid_graph(n)
    GraphSet.set_universe(universe)
    start, goal = 1, n * n * n
    paths = GraphSet.paths(start, goal, is_hamilton=True)
    return paths.len()

print([A(n) for n in range(2, 4)])

出力結果

[6, 38256]