Klasa Perm

WPROWADZENIE

Permutacja liczb od 0 do N-1 będzie instancją klasy Perm. Wewnętrznie przechowujemy permutację jako listę o długości N.

IMPLEMENTACJA

# Moduł perms.py

class Perm:
    """Klasa reprezentująca permutacje."""

    def __init__(self, size, data=None):
        """Konstruktor permutacji."""
        self.size = size
        if data:
            if self.size != len(data):
                raise ValueError("different size and len(data)")
            self.data = list(data)
        else:
            self.data = list(range(self.size))

    def __str__(self):
        """Napis odpowiadający liście wewnętrznej w permutacji."""
        return str(self.data)

    def __repr__(self):
        """Reprezentacja napisowa permutacji."""
        return "Perm({}, data={})".format(self.size, self.data)

    def __mul__(self, other):
        """Mnożenie dwóch permutacji."""
        if self.size != other.size:
            raise ValueError("different size")
        new_perm = Perm(self.size)
        for i in range(new_perm.size):
            new_perm.data[i] = self.data[other.data[i]]
        return new_perm

    def __invert__(self):
        """Zwraca permutację odwrotną (~perm)."""
        new_perm = Perm(self.size)
        for i in range(new_perm.size):
            new_perm.data[self.data[i]] = i
        return new_perm

    def label(self):
        """Tworzenie etykiety dla permutacji, nie działa dla size > 36."""
        if self.size > 36:
            raise ValueError("problem with labels")
        letters = "0123456789abcdefghijklmnopqrstuvwxyz"
        tmp = []
        for item in self.data:
            tmp.append(letters[item])
        return "".join(tmp)

    def is_identity(self):
        """Zwraca True, jeżeli permutacja jest identycznością."""
        return all(self.data[i] == i for i in range(self.size))

    def __cmp__(self, other):   # tylko Python 2
        """Porównywanie permutacji (leksykograficzne)."""
        return cmp(self.data, other.data)   # porównywanie list (szybsze)

    def max(self):
        """Return the highest element moved by the perm."""
        j_max = 0
        for j in range(self.size):
            if self.data[j] != j:
                j_max = j
        return j_max

    def min(self):
        """Return the lowest element moved by the perm."""
        j_min = 0     # zero będzie też dla identyczności
        for j in range(self.size):
            if self.data[j] != j:
                j_min = j
                break
        return j_min

    def __hash__(self):
        """Hashable perms."""
        return hash(tuple(self.data))

class TestPerm(unittest.TestCase):

    def setUp(self):
        self.N = 4
        self.E = Perm(self.N)
        self.H = Perm(self.N, [1, 3, 0, 2])

    def test_init(self):
        self.assertEqual(self.H, Perm(self.N, data=[1, 3, 0, 2]))
        self.assertRaises(ValueError, lambda: Perm(2, data=[0, 1, 2]))

    def test_repr(self):
        self.assertEqual(repr(self.E), "Perm(4, data=[0, 1, 2, 3])")
        self.assertEqual(repr(self.H), "Perm(4, data=[1, 3, 0, 2])")

    def test_label(self):
        self.assertEqual(self.E.label(), "0123")
        self.assertEqual(self.H.label(), "1302")

    def test_identity(self):
        self.assertTrue(self.E.is_identity())
        self.assertFalse(self.H.is_identity())

    def test_mul(self):
        self.assertEqual(self.E * self.E, self.E)
        self.assertEqual(self.E * self.H, self.H)
        self.assertNotEqual(self.H * self.H, self.H)
        self.assertRaises(ValueError, lambda: Perm(2) * Perm(1))

    def test_invert(self):
        self.assertEqual(~self.E, self.E)
        self.assertEqual(~self.H, Perm(self.N, [2, 0, 3, 1]))
        self.assertEqual(self.H * (~self.H), self.E)

    def test_cmp(self):
        self.assertFalse(self.H == self.E)
        self.assertTrue(self.E < self.H)
        self.assertTrue(self.H < self.H * self.H)

    def test_min_max(self):
        self.assertEqual(self.H.min(), 0)
        self.assertEqual(self.H.max(), 3)
        self.assertEqual(self.E.min(), 0)
        self.assertEqual(self.E.max(), 0)

    def test_hash(self):
        aset = set()
        aset.add(self.E)
        aset.add(self.E)  # ignored
        self.assertEqual(len(aset), 1)
        aset.add(self.H)
        aset.add(self.H)  # ignored
        self.assertEqual(len(aset), 2)

    def tearDown(self): pass

# Przykład zastosowania.

N = 4                         # permutacje liczb od 0 do 3
E = Perm(N)                   # identyczność
H = Perm(N, [1, 3, 0, 2])
print("identity {} {}".format(E.is_identity(), H.is_identity()))   # True, False
print("str {} {}".format(E, H))   # [0, 1, 2, 3] [1, 3, 0, 2]
print("label {} {}".format(E.label(), H.label()))   # 0123, 1302
print("invert {} {} {}".format(H, ~H, H*(~H)))
print("cmp {}".format(H < H*H))   # True