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)