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.
__call__
,__mul__
and__eq__
methods and what data structure to use to store permutation itself. \$\endgroup\$ – Montreal Apr 23 '18 at 5:58