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.
1 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.
__call__,__mul__and__eq__methods and what data structure to use to store permutation itself. \$\endgroup\$