Skip to content

Instantly share code, notes, and snippets.

@nealeyoung
Created April 7, 2025 10:56
Show Gist options
  • Save nealeyoung/dcaae16baa320f12a10c57b71b7dea62 to your computer and use it in GitHub Desktop.
Save nealeyoung/dcaae16baa320f12a10c57b71b7dea62 to your computer and use it in GitHub Desktop.
from functools import cache, cmp_to_key
from itertools import permutations as it_permutations
from typing import Final, Generator, Iterable, Self
Allocation = tuple[int, ...]
class Permutation:
def __init__(self, perm: Iterable[int]) -> None:
self.perm: Final = tuple(perm)
self.length: Final[int] = len(self.perm)
r = [0] * self.length
for i, p in enumerate(self.perm):
r[p] = i
self.ranks: Final = tuple(r)
def __hash__(self) -> int:
return hash(self.perm)
def __len__(self) -> int:
return self.length
@cache
def delete(self, i: int) -> Self:
return permutation(p - int(p > i) for p in self.perm if p != i)
@cache
def _alloc_to_ranks(self, alloc: Allocation) -> list[int]:
return sorted(self.ranks[i] for i in alloc)
@cache
def alloc_cmp(self, alloc1: Allocation, alloc2: Allocation) -> int:
if alloc1 == alloc2:
return 0
r1 = self._alloc_to_ranks(alloc1)
r2 = self._alloc_to_ranks(alloc2)
if all(i <= j for i, j in zip(r1, r2)):
return -1
if all(i >= j for i, j in zip(r1, r2)):
return 1
raise ValueError(f"incomparable allocations({self.perm}): {alloc1}, {alloc2}")
@property
def alloc_key(self):
return cmp_to_key(self.alloc_cmp)
def permutation(p: Iterable[int]) -> Permutation:
return _permutation(tuple(p))
@cache
def _permutation(p: tuple[int]) -> Permutation:
return Permutation(p)
def permutations(n: int) -> Generator[Permutation, None, None]:
for p in it_permutations(range(n)):
yield permutation(p)
@cache
def identity(n: int) -> Permutation:
return permutation(range(n))
@cache
def undelete_from_allocation(alloc: Iterable[int], i: int) -> tuple[int, ...]:
return tuple(a + int(a >= i) for a in alloc)
class Tree:
def __init__(self, perms: tuple[Permutation, ...]):
assert perms
self.perms = perms
self.outcome = tuple(() for _ in perms)
self.best_i = None
self.is_leaf = False
self.incomparable = False
self.i_to_incomparable = None
if not perms[0]:
assert not any(perms)
self.is_leaf = True
return
self.subtrees = sts = {}
self.outcomes = outs = {}
perm0, *rest = perms
for i in perm0.perm:
sts[i] = t = tree(tuple(p.delete(i) for p in rest) + (perm0.delete(i),))
if t.contains_incomparable:
self.i_to_incomparable = i
outcome = t.outcome
outs[i] = (((i,) + undelete_from_allocation(outcome[-1], i),) + tuple(
undelete_from_allocation(a, i) for a in outcome[:-1]
))
if self.i_to_incomparable is not None:
return
try:
self.best_i = min(perm0.perm, key=lambda i1: perm0.alloc_key(outs[i1][0]))
self.outcome = outs[self.best_i]
except ValueError:
self.incomparable = True # self.outcome is (), ()
@property
def contains_incomparable(self) -> bool:
return not self.is_leaf and (self.incomparable or self.i_to_incomparable is not None)
def dump_incomparable(self):
assert self.contains_incomparable
if self.incomparable:
print("children of", ", ".join(f"{p.perm}" for p in self.perms), ":")
for i in self.perms[0].perm:
print(f" {i}: {self.outcomes[i]}")
else:
print(f"i_to_incomparable: {self.i_to_incomparable}")
self.subtrees[self.i_to_incomparable].dump_incomparable()
@cache
def tree(perms: tuple[Permutation, ...]) -> Tree:
return Tree(perms)
def main() -> None:
for n in range(3, 10):
for p1 in permutations(n):
for p2 in permutations(n):
t = tree((identity(n), p1, p2))
if t.contains_incomparable:
print(f"{n} incomparable found:")
t.dump_incomparable()
return
print(f"{n} no incomparable found")
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment