Python class for permutations

Question

I am trying to develop a program which will solve any permutation-based puzzle such as 15 puzzle or Rubik's cube, so there will be a follow-up question about class that actually solves puzzle. Here I ask about the class which is essential to this task: Permutation class.

class Permutation(object):
    @staticmethod
    def get_letter_id(num):
        """
        Returns an identity permutation of first :num: number of 
        uppercase ASCII letters.
        """
        letters = string.ascii_uppercase[:num]

        return Permutation(tuple(zip(letters, letters)), "Id" + str(num))

    def __init__(self, perm, label=""):
        """
        :param perm: List of tuples of type (A, B), which shows that in given sequence of symbols
                        symbol A will be replaced by symbol B
        :param label: Label for better (or worse) representation. 
        """
        top_symbols = [p[0] for p in perm]
        bottom_symbols = [p[1] for p in perm]

        top_symbols = set(top_symbols)
        bottom_symbols = set(bottom_symbols)

        if top_symbols != bottom_symbols:
            raise Exception("Incorrect Permutation")

        self._perm = list(perm)
        self._perm.sort(key=lambda x: x[0])
        self._label = str(label)

    @property
    def inverse(self):
        p = [(p[1], p[0]) for p in self._perm]
        p.sort(key=lambda x: x[0])
        return Permutation(p, "Inverse({0})".format(self._label))

    @property
    def parity(self):
        return self._inversions % 2

    @property
    def symbols(self):
        return sorted([i for i, j in self._perm])

    @property
    def _inversions(self):
        res = 0
        top = [i for i, j in self._perm]
        bottom = [j for i, j in self._perm]
        for i in range(len(top)):
            for j in range(i, len(top)):
                if bottom[i] > bottom[j]:
                    res += 1
        return res

    def print_carrier(self):
        [print("{0} -> {1}".format(mutation[0], mutation[1])) for mutation in self._perm if mutation[0] != mutation[1]]

    def _find_symbol(self, symbol):
        for i in range(len(self._perm)):
            if self._perm[i][0] == symbol:
                return i
        raise Exception("Can't find given symbol in permutation.")

    def __call__(self, sequence):
        """
        Applies this permutation to the given sequence of symbols.
        For performance reasons this permutation assumed applicable to given sequence.
        """
        return tuple([self._perm[self._find_symbol(symbol)][1] for symbol in sequence])

    def __eq__(self, permutation):
        if type(permutation) != Permutation:
            return False
        condition1 = self.symbols == permutation.symbols
        condition2 = self.__call__(self.symbols) == permutation(self.symbols)
        return condition1 and condition2

    def __mul__(self, permutation):
        first = [mutation[0] for mutation in self._perm]
        second = self.__call__(permutation(first))
        return Permutation(tuple(zip(first, second)), str(self) + " * " + str(permutation))

    def __repr__(self):
        return self._label

Performance should not be ignored too.

Answer 1

    def __init__(self, perm, label=""):
        """
        :param perm: List of tuples of type (A, B), which shows that in given sequence of symbols
                        symbol A will be replaced by symbol B
        :param label: Label for better (or worse) representation. 
        """
        top_symbols = [p[0] for p in perm]
        bottom_symbols = [p[1] for p in perm]

        top_symbols = set(top_symbols)
        bottom_symbols = set(bottom_symbols)

        if top_symbols != bottom_symbols:
            raise Exception("Incorrect Permutation")

That's an important check, but not a sufficient one. If I pass [(1, 1), (2, 1), (2, 2)] then top_symbols and bottom_symbols will be the same set, but it's not a valid permutation.

---

    @property
    def inverse(self):
        p = [(p[1], p[0]) for p in self._perm]
        p.sort(key=lambda x: x[0])
        return Permutation(p, "Inverse({0})".format(self._label))

Why sort p? The constructor does that anyway.

---

    @property
    def symbols(self):
        return sorted([i for i, j in self._perm])

Why sorted? The constructor does that already.

Also, why do some methods use [something involving p[i] for p in self._perm] and others [something involving i and/or j for i, j in self._perm])?

---

    @property
    def _inversions(self):
        res = 0
        top = [i for i, j in self._perm]
        bottom = [j for i, j in self._perm]
        for i in range(len(top)):
            for j in range(i, len(top)):
                if bottom[i] > bottom[j]:
                    res += 1
        return res

This takes \$O(n^2)\$ time. There are \$O(n \lg n)\$ algorithms to do it, so since you say that performance is a concern you probably want to revisit this method.

---

    def print_carrier(self):
        [print("{0} -> {1}".format(mutation[0], mutation[1])) for mutation in self._perm if mutation[0] != mutation[1]]

The name is somewhat opaque: carrier?!

The implementation is also somewhat hacky. As far as I can tell without executing to double-check, this is using a list comprehension purely to iterate and produce side effects. Ugh.

---

    def _find_symbol(self, symbol):
        for i in range(len(self._perm)):
            if self._perm[i][0] == symbol:
                return i

Whoa! If this method is used much at all, it's going to be a major performance hit. IMO you need to revisit the way the data is stored: to do this efficiently you want a dict.

Also: why return i? Under what circumstances would you call this method wanting anything other than self._perm[i][1]?

---

    def __eq__(self, permutation):
        if type(permutation) != Permutation:
            return False
        condition1 = self.symbols == permutation.symbols
        condition2 = self.__call__(self.symbols) == permutation(self.symbols)
        return condition1 and condition2

Why not just do an equality check on _perm and permutation._perm?

---

    def __mul__(self, permutation):
        first = [mutation[0] for mutation in self._perm]
        second = self.__call__(permutation(first))
        return Permutation(tuple(zip(first, second)), str(self) + " * " + str(permutation))

Firstly, DRY: first is self.symbols. Secondly, IMO a comprehension for second would be more clearly checkable against the definition of permutation composition. Thirdly, why tuple(...) in the call to the constructor? If zip works in get_letter_id it should work here too.