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"
        word = []
        for item in self.data:
            word.append(letters[item])
        return "".join(word)

    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

    def __eq__(self, other):
        """Porównywanie permutacji (perm1 == perm2)."""
        return other.data == self.data

    def __ne__(self, other):
        """Porównywanie permutacji (perm1 != perm2)."""
        return not self == other

    def __lt__(self, other):
        """Porównywanie permutacji (perm1 < perm2)."""
        return self.data < other.data

    def __le__(self, other):
        """Porównywanie permutacji (perm1 <= perm2)."""
        return self.data <= other.data

    def __gt__(self, other):
        """Porównywanie permutacji (perm1 > perm2)."""
        return self.data > other.data

    def __ge__(self, other):
        """Porównywanie permutacji (perm1 >= perm2)."""
        return self.data >= other.data

    def max(self):
        """Zwraca największy element przesunięty przez permutację."""
        j_max = 0
        for j in range(self.size):
            if self.data[j] != j:
                j_max = j
        return j_max

    def min(self):
        """Zwraca najmniejszy element przesunięty przez permutację."""
        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):
        """Hash dla permutacji."""
        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])
assert E.is_identity()
assert not H.is_identity()
assert str(E) == "[0, 1, 2, 3]"
assert str(H) == "[1, 3, 0, 2]"
assert str(~H) == "[2, 0, 3, 1]"
assert E.label() == "0123"
assert H.label() == "1302"
assert H * (~H) == E
assert H < H * H   # porównywanie