https://github.com/emarberg/virtual-permutations
Tip revision: e45c307a4731bedf4fcb0393d5ddb69ea863f63a authored by Eric Marberg on 23 March 2020, 06:38:45 UTC
fixed typo
fixed typo
Tip revision: e45c307
affine.py
from virtual import VirtualInvolution, VirtualPermutation
from collections import defaultdict
REDUCED_WORDS_CACHE = {}
INVOLUTION_WORDS_CACHE = {}
class AffinePermutation(object):
"""
Simple class implementing affine permutations, primarily used for testing.
"""
def __init__(self, *oneline):
if len(oneline) == 1 and type(oneline[0]) != int:
oneline = [i for i in oneline[0]]
n = len(oneline)
assert n >= 2
assert list(sorted(i % n for i in oneline)) == list(range(n))
offset = (sum(oneline) - (n - 1) * n // 2) // n
self.oneline = n * [0]
for i in range(n):
q = (i - offset) // n
r = (i - offset) % n
self.oneline[i] = oneline[r] + q * n
self.oneline = tuple(self.oneline)
self.rank = n
self._cycle_set = None
self._right_descent_set = None
self._left_descent_set = None
self._code = None
@classmethod
def identity(cls, rank):
oneline = list(range(rank))
return AffinePermutation(oneline)
@classmethod
def simple_transposition(cls, i, rank):
return AffinePermutation.transposition(i, i + 1, rank)
@classmethod
def transposition(cls, i, j, rank):
if j > i:
i, j = j, i
assert (j - i) % rank != 0
oneline = list(range(i, i + rank))
oneline[0] = j
oneline[(j - i) % rank] = i - ((j - i) // rank) * rank
return AffinePermutation(oneline)
def star(self):
return AffinePermutation(reversed([self.rank + 1 - i for i in self.oneline]))
def __call__(self, i):
q = i // self.rank
r = i % self.rank
return self.oneline[r] + q * self.rank
def inverse(self):
oneline_map = {}
for i in range(self.rank):
x = self(i)
q = x // self.rank
r = x % self.rank
oneline_map[r] = i - q * self.rank
assert set(oneline_map.keys()) == set(range(self.rank))
oneline = [oneline_map[i] for i in range(self.rank)]
return AffinePermutation(*oneline)
def __mul__(self, other):
assert self.rank == other.rank
assert type(other) == AffinePermutation
newline = [self(other(i)) for i in range(self.rank)]
return AffinePermutation(*newline)
def __pow__(self, e):
assert type(e) == int
if e < 0:
return self.inverse()**(-e)
elif e == 0:
return AffinePermutation(range(self.rank))
elif e % 2 == 1:
return self * self**(e - 1)
else:
w = self**(e // 2)
return w * w
def __mod__(self, other):
# the magic function % implements the Demazure product for affine permuations
assert type(other) == AffinePermutation
assert other.rank == self.rank
ans = self
for i in other.get_reduced_word():
if i not in ans.right_descent_set:
ans *= AffinePermutation.simple_transposition(i, self.rank)
return ans
def __lt__(self, other):
"""Determines lexicographic order on one-line representation."""
assert type(other) == AffinePermutation
assert self.rank == other.rank
for i in range(1, self.rank + 1):
if self(i) > other(i):
return False
if self(i) < other(i):
return True
return False
def __eq__(self, other):
assert type(other) == AffinePermutation
assert self.rank == other.rank
return self.oneline == other.oneline
def __ne__(self, other):
return not (self == other)
def __repr__(self):
n = self.rank
s = [
'...',
', '.join(map(str, [self(-n + i + 1) for i in range(n)])),
', '.join(map(str, [self(i + 1) for i in range(n)])),
', '.join(map(str, [self(n + i + 1) for i in range(n)])),
'...'
]
return '[ ' + ' | '.join(s) + ' ]'
def __hash__(self):
return hash(self.oneline)
@property
def code(self):
if self._code is None:
code = []
for i in range(1, 1 + self.rank):
c = 0
for j in range(i + 1, self.rank + i):
if self(j) < self(i):
c += (self(i) - self(j)) // self.rank + 1
code += [c]
self._code = tuple(code)
return self._code
def __len__(self):
return sum(self.code)
@classmethod
def from_code(cls, code):
assert all(i >= 0 for i in code) and not all(i > 0 for i in code)
n = len(code)
indices = [i for i in range(n) if code[i] != 0 and code[(i + 1) % n] == 0]
if indices:
i = indices[0]
newcode = list(code)
newcode[(i + 1) % n], newcode[i] = newcode[i] - 1, 0
return cls.from_code(newcode) * AffinePermutation.simple_transposition(i + 1, n)
return AffinePermutation.identity(n)
@classmethod
def all(cls, n, length_bound=None, finite=False):
def increment_fn(w, i):
return w * cls.simple_transposition(i, n)
for w in cls._generate(n, cls.identity(n), increment_fn, length_bound, finite):
yield w
@classmethod
def involutions(cls, n, involution_length_bound=None, finite=False):
def increment_fn(w, i):
return cls.simple_transposition(i, n) % w % cls.simple_transposition(i, n)
for w in cls._generate(n, cls.identity(n), increment_fn, involution_length_bound, finite):
yield w
@classmethod
def _generate(cls, n, start, increment_fn, length_bound, finite):
level, next_level, length = {start}, set(), 0
while level:
for w in level:
if length_bound is None or length < length_bound:
next_level |= {increment_fn(w, i) for i in w.right_ascent_set if not (finite and i == n)}
yield w
level, next_level, length = next_level, set(), length + 1
@property
def length(self):
return len(self)
@property
def absolute_length(self):
return self.rank - len(self.cycle_set)
@property
def involution_length(self):
if self.is_involution():
return (self.length + self.absolute_length) // 2
def is_involution(self):
return all(self(self(i)) == i for i in range(self.rank))
def is_identity(self):
return len(self) == 0
@property
def cycle_set(self):
if self._cycle_set is None:
self._cycle_set = set()
remaining = set(range(self.rank))
while len(remaining) > 0:
i = min(remaining)
remaining.remove(i)
cycle = [i]
while True:
j = self(cycle[-1])
if cycle[0] == j:
break
remaining.remove(j % self.rank)
cycle.append(j)
self._cycle_set.add(tuple(cycle))
return self._cycle_set
@property
def right_descent_set(self):
if self._right_descent_set is None:
self._right_descent_set = set()
for i in range(1, self.rank + 1):
if(self(i) > self(i + 1)):
self._right_descent_set.add(i)
return self._right_descent_set
@property
def left_descent_set(self):
if self._left_descent_set is None:
self._left_descent_set = self.inverse().right_descent_set
return self._left_descent_set
@property
def right_ascent_set(self):
return set(range(1, self.rank + 1)) - self.right_descent_set
@property
def left_ascent_set(self):
return set(range(1, self.rank + 1)) - self.left_descent_set
def is_right_descent(self, i):
return i in self.right_descent_set
def is_left_descent(self, i):
return i in self.left_descent_set
def get_right_descent(self):
return min(self.right_descent_set) if self.right_descent_set else None
def get_left_descent(self):
return min(self.left_descent_set) if self.left_descent_set else None
def get_reduced_word(self):
i = self.get_right_descent()
if i is None:
return ()
w = self * AffinePermutation.simple_transposition(i, self.rank)
return w.get_reduced_word() + (i,)
@property
def reduced_words(self):
if self.oneline not in REDUCED_WORDS_CACHE:
if self.is_identity():
words = {()}
else:
words = set()
for i in self.right_descent_set:
s = AffinePermutation.simple_transposition(i, self.rank)
words |= {e + (i,) for e in (self * s).reduced_words}
REDUCED_WORDS_CACHE[self.oneline] = words
return REDUCED_WORDS_CACHE[self.oneline]
def get_involution_word(self):
return self.get_min_atom().get_reduced_word()
@property
def involution_words(self):
if self.is_involution():
oneline = tuple(self.oneline)
if oneline not in INVOLUTION_WORDS_CACHE:
INVOLUTION_WORDS_CACHE[oneline] = set()
for w in self.get_atoms():
INVOLUTION_WORDS_CACHE[oneline] |= w.reduced_words
return INVOLUTION_WORDS_CACHE[oneline]
def is_finite_type(self):
return all(1 <= self(i + 1) <= self.rank for i in range(self.rank))
def is_atom(self):
z = self.inverse() % self
return z.involution_length == self.length
def get_min_atom(self):
assert self.is_involution()
oneline = []
for i in range(1, self.rank + 1):
if i < self(i):
oneline += [self(i), i]
elif i == self(i):
oneline += [i]
return AffinePermutation(oneline).inverse()
def get_max_atom(self):
assert self.is_involution()
oneline = []
for j in range(1, self.rank + 1):
if self(j) < j:
oneline += [j, self(j)]
elif j == self(j):
oneline += [j]
return AffinePermutation(oneline).inverse()
def get_atoms(self):
assert self.is_involution()
level = {self.get_min_atom().inverse()}
while level:
next_level = set()
for w in level:
yield w.inverse()
for i in range(1, self.rank + 1):
c, a, b = w(i), w(i + 1), w(i + 2)
if a < b < c:
s = AffinePermutation.simple_transposition(i, self.rank)
t = AffinePermutation.simple_transposition(i + 1, self.rank)
next_level.add(w * t * s)
level = next_level
def virtualize(self, i, j, invol):
assert type(i) == type(j) == int and type(invol)== AffinePermutation
assert i < j
assert i % invol.rank != j % invol.rank
assert invol(i) == j or invol(i) % invol.rank != j % invol.rank
assert self.rank == invol.rank
assert invol.is_involution()
w, n = self.inverse(), self.rank
inputs = sorted({self(i), self(j), self(invol(i)), self(invol(j))})
outputs = [w(x) for x in inputs]
inputs_index = {v: i + 1 for i, v in enumerate(inputs)}
outputs_index = {v: i + 1 for i, v in enumerate(sorted(outputs))}
mirror_extensions = defaultdict(set)
double_extensions = defaultdict(set)
single_extensions = defaultdict(set)
lower = min(min(inputs) - max(inputs), min(outputs) - max(outputs)) // n - 1
upper = max(max(inputs) - max(outputs), max(outputs) - min(outputs)) // n + 2
for k in range(lower, upper):
shifted = [x + k * n for x in inputs]
if set(inputs) & set(shifted):
continue
new_inputs = sorted(inputs + shifted)
new_outputs = [w(x) for x in new_inputs]
base = tuple(inputs_index[x] if x in inputs else -inputs_index[x - k * n] for x in new_inputs)
pi = tuple(outputs_index[x] if x in outputs else -outputs_index[x - k * n] for x in new_outputs)
mirror_extensions[base].add(pi)
lower = min(inputs)
while any(invol(x) > min(inputs) or max(w(x), w(invol(x))) > min(outputs) for x in range(lower, lower + n)):
lower -= n
upper = max(inputs) + 1
while any(invol(x) < max(inputs) or min(w(x), w(invol(x))) < max(outputs)for x in range(upper - n, upper)):
upper += n
for x in range(lower, upper):
if x % n in {z % n for z in inputs}:
continue
if w(x) == invol(w(x)):
new_outputs = [w(z) for z in sorted(inputs + [x])]
def format_output(z):
ch = VirtualPermutation.FIXED_CHAR
return outputs_index[z] if z in outputs else ch
base = tuple(map(format_output, sorted(new_outputs)))
pi = tuple(map(format_output, new_outputs))
single_extensions[base].add(pi)
if w(x) < invol(w(x)):
y = self(invol(w(x)))
new_outputs = [w(z) for z in sorted(inputs + [x, y])]
def format_output(z):
ch1, ch2 = VirtualPermutation.CYCLE_CHARS
return outputs_index[z] if z in outputs else (ch1 if z == w(x) else ch2)
base = tuple(map(format_output, sorted(new_outputs)))
pi = tuple(map(format_output, new_outputs))
double_extensions[base].add(pi)
order = tuple(outputs_index[x] for x in outputs)
return VirtualPermutation(order, mirror_extensions, double_extensions, single_extensions)