trjhtr

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.

 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.