# Python class for permutations

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.

• What are you asking, more specifically? Should the style of the code be reviewed, or the performance, or the logic (or all of them)?
– maxb
Apr 19, 2018 at 8:54
• @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. Apr 23, 2018 at 5:58

    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.