presenting… 30

gifted python code

carina · mass tech

2021-06-29

so i was visiting the duluth reu as i do most years and carina asked me about her project related to arXiv:1606.09643 and arXiv:2104.03890. of course i still have the program that i wrote for her, even though i don't remember what it does.

from typing import List, Tuple
import sys
import itertools
from functools import lru_cache

Perm = Tuple[int, ...]


@lru_cache()
def inverse(perm: Perm) -> Perm:
    n = len(perm)
    ret: List[int] = [0] * n
    for i in range(n):
        ret[perm[i] - 1] = i + 1
    return tuple(ret)


@lru_cache()
def carina_pop_original(perm: Perm) -> Perm:
    ret: List[int] = []
    n = len(perm)
    i = 0
    while i < n:
        j = i
        while j + 1 < n and perm[j] > perm[j + 1]:
            j += 1
        ret += list(perm[i : j + 1][::-1])
        i = j + 1
    return tuple(ret)


@lru_cache()
def carina_pop(perm: Perm) -> Perm:
    return inverse(carina_pop_original(inverse(perm)))


# --------


@lru_cache()
def carina_swap(perm: Perm) -> Perm:
    n = len(perm)
    for x in range(1, n):  # x = 1, 2, ..., n-1
        j = perm.index(x)
        i = perm.index(x + 1)

        def blocks(k: int) -> bool:
            return (perm[k] < x and k % 2 == 0) or (perm[k] > x + 1 and k % 2 == 1)

        if j >= i + 2 and any(blocks(k) for k in range(i + 1, j)):
            ret = list(perm)
            ret[i] = x
            ret[j] = x + 1
            return tuple(ret)
    return perm


@lru_cache()
def carina_pi_down_original(perm: Perm):
    while (x := carina_swap(perm)) != perm:
        perm = x
    return perm


@lru_cache()
def carina_pi_down(perm: Perm):
    return carina_pi_down_original(perm)


@lru_cache()
def carina_func(perm: Perm):
    return carina_pi_down(carina_pop(perm))


def is_identity(perm: Perm):
    return all(perm[i] == i + 1 for i in range(len(perm)))


def check(perm: Perm):
    x = perm
    for _ in range(0, len(perm) - 2):
        x = carina_func(x)
    return is_identity(carina_func(x)) and not is_identity(x)


for perm in itertools.permutations(range(1, int(sys.argv[1]) + 1)):
    if perm != carina_pi_down(perm):
        continue
    x = perm
    count = 0
    while not is_identity(x):
        x = carina_func(x)
        count += 1
    print(count, perm)