1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ What are you asking, more specifically? Should the style of the code be reviewed, or the performance, or the logic (or all of them)? \$\endgroup\$ – maxb Apr 19 '18 at 8:54
  • \$\begingroup\$ @maxb, actually, I am interested in all of them (code style, performance and logic, though not all methods of this class need to be as fast as possible). The most questionable points are __call__, __mul__ and __eq__ methods and what data structure to use to store permutation itself. \$\endgroup\$ – Montreal Apr 23 '18 at 5:58
3
\$\begingroup\$
    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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.