groups-sampled.py

import operator
from abc import abstractmethod, ABC
from dataclasses import dataclass
from functools import reduce
from itertools import product, repeat
import random as rnd


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 Er(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, Er):
            return Er(i, self.n)
        else:
            return Es(i, self.n)


class Es(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, Er):
            return Es(i, self.n)
        else:
            return Er(i, self.n)


@dataclass
class D:
    n: int

    def __post_init__(self):
        self.order = self.n
        self.r = lambda: (Er(r, self.n) for r in range(self.n))
        self.s = lambda: (Es(s, self.n) for s in range(self.n))
        self.id = Er(0, self.n)

    def __iter__(self):
        for r in self.r():
            yield r
        for s in self.s():
            yield s

    def __mul__(self, other):
        return DP(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)

    def __iter__(self):
        return self.elems()

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

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


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

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

    def __iter__(self):
        return self.elems()

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


class Perm(Element):
    def __init__(self, i, n):
        super().__init__()
        self.i, self.n = i, 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 Et(Element):
    def __init__(self, *items):
        super().__init__()
        self.items = items

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

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


def iterSample(iterable, samplesize):
    """https://stackoverflow.com/a/12581484/9681577"""
    results = []
    for i, v in enumerate(iterable):
        r = rnd.randint(0, i)
        if r < samplesize:
            if i < samplesize:
                results.insert(r, v)  # add first samplesize items in random order
            else:
                results[r] = v  # at a decreasing rate, replace random items
    if len(results) < samplesize:
        raise ValueError("Sample larger than population.")
    return results


h, h2 = {}, {}
G = S(5) * S(7) * S(8)
print(f"order of {G}: {G.order}")
for a in iterSample(G.lazyelems(), 1000000):
    a = a()
    r = a
    i = 1
    ss = {G.id}
    while r not in ss:
        ss.add(r)
        i += 1
        r = r * a
    if r == G.id:
        # print(f"{a} order: {i}", r, G.id)
        if i not in h:
            h[i] = 0
        h[i] += 1
    else:
        if i not in h2:
            h2[i] = 0
        h2[i] += 1
best = max(h.keys())
print(
    f"{str(G).ljust(20, ' ')}   order {G.order:15}   best_order: "
    f"{best:10} ({h[best]:12})   P: {max(h.values()) / sum(h.values()):.4f}  {h2}   {h}")