groups.py

import operator
import random as rnd
from abc import abstractmethod, ABC
from dataclasses import dataclass
from functools import reduce
from itertools import product, islice, cycle
from math import log, factorial
from time import sleep


class Element(ABC):
    i: int

    def __init__(self):
        self.sym = self.__class__.__name__.lower()

    @abstractmethod
    def __mul__(self, other):
        pass

    def __repr__(self):
        return f"{self.sym}{self.i}"

    def __eq__(self, other):
        return repr(self) == repr(other)

    def __hash__(self):
        return hash(repr(self))


class RElem(Element):
    def __init__(self, i, n):
        super().__init__()
        self.i, self.n = i, n

    def __mul__(self, other):
        i = (self.i + other.i) % self.n
        if isinstance(other, RElem):
            return RElem(i, self.n)
        else:
            return SElem(i, self.n)


class SElem(Element):
    def __init__(self, i, n):
        super().__init__()
        self.i, self.n = i, n

    def __mul__(self, other):
        i = (self.i - other.i) % self.n
        if isinstance(other, RElem):
            return SElem(i, self.n)
        else:
            return RElem(i, self.n)


@dataclass
class D:
    n: int

    def __post_init__(self):
        self.order = self.n * 2
        self.r = lambda: (RElem(r, self.n) for r in range(self.n))
        self.s = lambda: (SElem(s, self.n) for s in range(self.n))
        self.id = RElem(0, self.n)
        self.bits = int(log(self.order, 2))

    def __iter__(self):
        if self.order < 100_000:
            yield from self.r()
            yield from self.s()
        else:
            for i in range(self.order):
                yield rnd.choice([RElem, SElem])(rnd.getrandbits(self.bits), self.n)

    def __mul__(self, other):
        return DProd(self, other)

    def __repr__(self):
        return f"D{self.n}"


@dataclass
class S:
    n: int

    def __post_init__(self):
        self.order = reduce(operator.mul, range(1, self.n + 1))
        self.elems = lambda: (Perm(i, self.n) for i in range(self.order))
        self.id = Perm(0, self.n)
        self.bits = int(log(self.order, 2))

    def __iter__(self):
        if self.order < 100_000:
            yield from self.elems()
        else:
            for i in range(self.order):
                yield Perm(rnd.getrandbits(self.bits), self.n)

    def __mul__(self, other):
        return DProd(self, other)

    def __repr__(self):
        return f"S{self.n}"


class DProd:
    def __init__(self, *groups):
        self.order = reduce(operator.mul, [g.order for g in groups])
        self.groups = groups
        self.elems = lambda: (TupElem(*es) for es in product(*self.groups))
        self.id = TupElem(*(g.id for g in self.groups))

    def __iter__(self):
        if self.order < 100_000:
            yield from self.elems()
        else:
            its = [cycle(iter(g)) for g in self.groups]
            for i in range(self.order):
                yield TupElem(*(next(it) for it in its))

    def __repr__(self):
        return "×".join([str(g) for g in self.groups])

    def __mul__(self, other):
        if isinstance(other, DProd):
            return DProd(*self.groups, *other.groups)
        return DProd(*self.groups, other)


@dataclass
class Z:
    n: int

    def __post_init__(self):
        self.order = self.n
        self.elems = lambda: (NatElem(i, self.n) for i in range(self.order))
        self.id = NatElem(0, self.n)
        self.bits = int(log(self.order, 2))

    def __iter__(self):
        if self.order < 100_000:
            yield from self.elems()
        else:
            for i in range(self.order):
                yield NatElem(rnd.getrandbits(self.bits), self.n)

    def __mul__(self, other):
        return DProd(self, other)

    def __repr__(self):
        return f"Z{self.n}"


class NatElem(Element):
    def __init__(self, i, n):
        super().__init__()
        self.i, self.n = i, n
        self.order = n

    def __mul__(self, other):
        return NatElem((self.i + other.i) % self.n, self.n)

    def __repr__(self):
        return f"{self.i}"


class Perm(Element):
    def __init__(self, i, n):
        super().__init__()
        self.i, self.n = i, n
        self.order = factorial(n)
        available = list(range(n))
        mat = []
        for div in range(n, 0, -1):
            i, r = divmod(i, div)
            mat.append(available.pop(r))
        mat.extend(available)
        self.perm = mat

    def __mul__(self, other):
        perm = [self.perm[x] for x in other.perm]
        radix = self.n
        available = list(range(self.n))
        i = 1
        res = 0
        for row in perm:
            idx = available.index(row)
            del available[idx]
            res += idx * i
            i *= radix
            radix -= 1
        return Perm(res, self.n)

    def __repr__(self):
        return f"{self.perm}"


class TupElem(Element):
    def __init__(self, *items):
        super().__init__()
        self.items = items
        itemsrv = list(reversed(items))
        lst = zip([1] + [(elema.order) for elema in itemsrv[:-1]], [elemb.i for elemb in itemsrv])
        self.i = sum(x * y for x, y in lst)

    def __mul__(self, other):
        return TupElem(*(a * b for a, b in zip(self.items, other.items)))

    def __repr__(self):
        return f"<{', '.join([str(a) for a in self.items])}>"


paths = {}
lim = 1_000_000_000
G = Z(1000000007) * S(28)
print(f"order of {G}: {G.order}", flush=True)
n = 1000
for a in islice(G, 0, n):
    r = a
    i = 1
    ss = set()
    path = 1
    while r != G.id:  # and i < lim:
        if r.i in ss:
            break
        path += 1
        ss.add(r.i)
        i += 1
        r = r * a
    print(f"order: {i}", a, '    ->    ', r, flush=True)
    if path not in paths:
        paths[path] = 0
    paths[path] += 1

    best = max(paths.keys())
    best2 = max(paths.keys())
    print(f"{str(G).ljust(18, ' ')}   max_order: {best2:10} ({paths[best2]:12})    {paths}", flush=True)

    good = sum((v for k, v in paths.items() if k >= min(best2, lim)))
    triviais = paths[1] if 1 in paths else 0
    print(f"good: {100 * good / sum(paths.values()):.18f}% self-inverses: {100 * triviais / sum(paths.values()):.18f}%")
    print(flush=True)

print("a comutar...", flush=True)
c = 0
for a, b in islice(zip(G, G), lim):
    if a * b == b * a:
        c += 1
print(f"commutativity: {c / lim:.18f}%", flush=True)


def factors(n):
    return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))