@nealyoung/

OvercookedMadCarat

Python

for https://cstheory.stackexchange.com/questions/2721/solving-all-marginals-problem-for-independent-sets-on-grid

fork
loading
Files
  • main.py
main.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#!/usr/bin/env python3

from functools import lru_cache

memoize = lru_cache(None)

N = 7
# N = 18

def nbrs1(x=0, on=0, n=N):
    if n <= 0:
        yield on
    else:
        yield from nbrs1(x, on, n-1)
        bit = 1 << (n-1)
        if not x & bit:
            yield from nbrs1(x, on | bit, n-2)


@memoize
def wt(i, x):
    '''return the weight of vertex v(i,x)'''
    return 1


@memoize
def P_in(i, x):
    assert 0 <= i
    return (
        wt(i, x) if i == 0 else
        wt(i, x) * sum(P_in(i-1, y) for y in nbrs1(x))
    )


@memoize
def P_out(i, x):
    assert i < N
    return (
        1 if i == N-1 else
        sum(wt(i+1, y) * P_out(i+1, y) for y in nbrs1(x))
    )


@memoize
def Q(i, x):
    return P_in(i, x) * P_out(i, x)


@memoize
def with_bit(j):
    return tuple(x for x in nbrs1() if x & (1 << j))


def all():
    return sum(Q(0, x) for x in nbrs1()) - 1


def prob(i, j):
    return sum(Q(i, x) for x in with_bit(j))


print("N =", N)
print("denominator =", all())
print()

for i in range(N):
    for j in range(N):
        print(prob(i, j), end=" ")
    print()

# N = 7
# denominator = 1280128949

# 402968942 298303063 333041917 316303258 333041917 298303063 402968942
# 298303063 296843520 279776968 292351405 279776968 296843520 298303063
# 333041917 279776968 296033698 285917681 296033698 279776968 333041917
# 316303258 292351405 285917681 293815906 285917681 292351405 316303258
# 333041917 279776968 296033698 285917681 296033698 279776968 333041917
# 298303063 296843520 279776968 292351405 279776968 296843520 298303063
# 402968942 298303063 333041917 316303258 333041917 298303063 402968942