@nealyoung/

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

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```