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)