Klasa Group (wersja 2)

WPROWADZENIE

https://arxiv.org/abs/math/9201304
D. E. Knuth, Efficient representation of perm groups, arXiv:math/9201304 [math.GR].

Przedstawiona implementacja jest działającą wersją roboczą.

IMPLEMENTACJA

Podana implementacja przy pierwszym przebiegu wyznacza zwykle zbyt dużą liczbę silnych generatorów. Dlatego warto uzyskane silne generatory wstawić jeszcze raz do algorytmu, w kolejności rosnącego perm.max().

from perms import Perm

class Group:
    """The class defining a perm group."""

    def __init__(self, size):
        """Load up a Group instance."""
        self.size = size   # rozmiar permutacji w grupie
        # Inicjalizacja struktur.
        self.Sigma = [(k+1) * [None] for k in range(self.size)]
        # Lista Sigma[k] zawiera co najmniej identyczność.
        for k in range(self.size):
            self.Sigma[k][k] = Perm(self.size)   # identyczność sigma_kk
        # Silne generatory.
        self.all_Sigma = [Perm(self.size)]   # E też dodam raz
        self.all_T = []

    def __str__(self):
        """Return a string representation of the group."""
        t = len(self.all_T)
        return "Group({}) with {} strong generators".format(self.size, t)

    def order(self):
        """Return the group order."""
        result = 1
        for k in range(self.size):
            result = result * sum(1 for perm in self.Sigma[k] if perm)
        return result

    def __contains__(self, perm):
        """ Test if the perm belongs to the group."""
        k = self.size - 1   # start od samej góry
        while k > 0:
            j = perm.data[k]
            if self.Sigma[k][j] is None:
                return False
            perm = ~self.Sigma[k][j] * perm
            k = k - 1
        return True

    def insert(self, perm):
        """The perm inserted into the group generates new 
        perms in order to satisfy the group properties."""
        if self.size != perm.size:
            raise ValueError("wrong size of the perm")
        self.alg_A(perm.max(), perm)

    def alg_A(self, k, perm):
        """Append the perm to the strong generators."""
        if perm in self:
            return
        j = perm.data[k]
        if self.Sigma[k][j] is not None:
            perm2 = ~self.Sigma[k][j] * perm
            # Trzeba się upewnić, jakiego rzędu jest perm.
            self.alg_A(perm2.max(), perm2)
            return
        self.all_T.append(perm)
        for item in self.all_Sigma:
            # Trzeba się upewnić, jakiego rzędu jest perm.
            perm2 = perm * item
            self.alg_B(perm2.max(), perm2)

    def alg_B(self, k, perm):
        """Update the Sigma."""
        if perm in self:
            return
        j = perm.data[k]
        if self.Sigma[k][j] is None:
            self.Sigma[k][j] = perm
            self.all_Sigma.append(perm)
            for item in self.all_T:
                # Trzeba się upewnić, jakiego rzędu jest perm.
                perm2 = item * perm
                k_max = perm2.max()
                if k_max != k:
                    self.alg_A(k_max, perm2)
                else:
                    self.alg_B(k_max, perm2)
            return
        item = ~self.Sigma[k][j] * perm
        # Trzeba się upewnić, jakiego rzędu jest perm.
        # Tu na pewno k_max < k.
        self.alg_A(item.max(), item)

    def iterperms(self):
        """The generator for perms from the group."""
        a = [0] * self.size
        while True:
            # M2. Odwiedziny.
            if all(self.Sigma[k][a[k]] is not None for k in range(self.size)):
                perm = Perm(self.size)
                for k in range(self.size):
                    perm = self.Sigma[k][a[k]] * perm
                yield perm
            # M3. Przygotowanie do dodania jedynki.
            j = self.size - 1
            # M4. Przeniesienie, jeśli trzeba.
            while a[j] == j and j >= 0:
                a[j] = 0
                j = j - 1
            # M5. Zwiększenie, o ile nie koniec.
            if j < 0:
                break
            else:
                a[j] = a[j] + 1

    def is_trivial(self):
        """Test if the group is trivial."""
        return self.order() == 1