from tqdm import tqdm
import itertools
from itertools import chain, combinations


def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))


for n in range(9):

    nodes = list(itertools.product(*(range(i, n) for i in range(n))))

    cnt = {v: 0 for v in nodes}

    cnt[tuple(range(n))] = 1

    for _ in range(n * (n - 1) // 2 + 3):
        print(n, _, sum(cnt.values()))
        cnt2 = {v: 0 for v in nodes}
        for a, b in tqdm(cnt.items()):
            for r in powerset(range(n)):
                for v in r:
                    if a[v] != v and a[v] not in r:
                        break
                else:
                    pt = list(a)
                    for v, nv in zip(r, r[1:]):
                        pt[v] = nv
                    pt = tuple(pt)
                    cnt2[pt] += b
        cnt = cnt2