Assignment #5: Algebraic Structures and Permutations

For this assignment, you will submit a single Python source file `a5.py`.

Your file may not import any modules or employ any external library functions associated with integers and sets (unless the problem statement explicitly permits this). You will be graded on the correctness, concision, and mathematical legibility of your code. The different problems and problem parts rely on each other; carefully consider whether you can use functions you define in one part within subsequent parts. You may reuse functions that you defined on previous assignments.

1. Suppose that we decide to represent permutations as lists of integers, such as `[2,1,0]`. For example, given some ordered list of elements such as `['a','b','c']`, after the permutation `[2,1,0]` is applied:
• the element `'a'`with index `0` in `['a','b','c']` should move to the location with index `2` in the result;
• the element `'b'`with index `1` in `['a','b','c']` should move to the location with index `1` in the result;
• the element `'c'`with index `2` in `['a','b','c']` should move to the location with index `0`.
1. Implement a function `permute()` that takes two arguments: a list `a` of length n and a permutation `p` on n elements. It should return the permuted list. For example:
`permute(['a','b','c'], [2,1,0]) # Should evaluate to ['c','b','a'].`

2. Implement a function `compose()` that takes two permutations `p1` and `p2`, both of the same length, and returns a single permutation that is the composition of those two permutations. That is, it returns a permutation `p3` that, when applied to a list, will produce the same result as applying the first permutation to the second permutation:
```# Should be "True" for any inputs if they are all of the same length.
permute(a, compose(p1,p2)) == permute(permute(a, p1), p2)```

3. Implement a function `composeList()` that takes as its one input a list of permutations, and returns a single permutation that is the result of composing the permutations in the list (according to the order they appear in the list).

4. Recall that for the set of permutations on n elements, the generating set can be the set of permutations that swap only two elements. Implement a function `generators()` that takes a single positive integer argument `n` and returns the set of generators for the set of permutations on n elements. An example is provided below.
```generators(4) # Should return {[1,0,2,3], [0,2,1,3], [0,1,3,2]}.
generators(5) # Should return {[1,0,2,3,4], [0,2,1,3,4], [0,1,3,2,4], [0,1,2,4,3]}.```
5. Implement a function `factor()` that takes a single permutation on n elements as an input and returns a list of generating permutations that can be composed to reconstruct it:
```# Should be "True" for any permutation "p".
composeList(factor(p)) == p```
See this fact about sorting algorithms for one approach that can be used to implement `factor()`.
```# Part (e).
def factor(p):
# If the permutation is the identity, return a list containing two
# instances of the same transposition.
if list(p) == list(range(len(p))):
transposition = list(p)
transposition[0:2] = [1, 0]
return [transposition, transposition]
factors = []
for i in range(0, len(p)):
if p[i] != i:
for j in range(0, len(p)):
if p[j] == i:
factors = factors + [swapTwo([x for x in range(0, len(p))], i, j)]
p[j] = p[i]
p[i] = i
# Reverse the list because the :func:`composeList` function expects the
# permutations to be applied from left to right (instead of right to left
# as in the mathematical definition of function composition).
return list(reversed(factors))```
2. Suppose that we use Python classes to represent algebraic structures, so that objects of those classes correspond to elements of the algebraic structures. We define the following superclass; all algebraic structures will be subclasses of this superclass.
```class AlgebraicStructure():
def __repr__(self):    return str(self)
def __str__(self):     return str(self.elem)
def __hash__(self):    return hash(self.elem)

def generators(self):  return {}
def associative(self): return False
def identity(self):    return None
def inverses(self):    return {}
def commutative(self): return False

def __eq__(x, y):
return x.elem == y.elem

def __init__(self, elem):
self.elem = elem

# Complete this function for #2.

# You may want to check wither either or both
# of the inputs "x" and "y" are simply members
# of the generating set, and transform them first
# to make your code more uniform.

return None```
It should be possible to define a new algebraic structure by defining a subclass and overloading a few of the member methods. For example, the following subclass represents a group with the generators `'a'`, `'b'`, and `'c'`:
```class G(AlgebraicStructure):
def generators(self):  return {'a','b','c'}
def associative(self): return True
def identity(self):    return 'c'
def inverses(self):    return {{'a','b'}, {'c','c'}}
def commutative(self): return True```
Complete the definition of the `__add__()` method so that it works in at least the following cases. That is, the `__add__()` should behave differently in all of these cases, and it should decide how to behave by calling the member methods `generators()`, `associative()`, `identity()`, `identity()`, `inverses()`, and `commutative()`.
1. If the algebraic structure is a free magma, use nested lists to represent an element.
2. If the algebraic structure is a commutative magma, use nested sets to represent an element.
3. If the algebraic structure is a free semigroup, use a single list to represent an element.
4. If the algebraic structure is a commutative semigroup, use a single set to represent an element.
5. If the algebraic structure is a monoid, do not store the identity element unless it is necessary.
6. If the algebraic structure is a group or commutative group, "cancel" as many elements with their inverses as possible in an element's representation.
```    def __add__(x, y):

# If the arguments are not from the same subclass,
# do not return a result.
if type(y) != type(x):
return None
constructor = type(x)
c = x

# Helper method for cancelling inverses in
# non-commutative structures.
def cancelNonCommutative(l):
repeat = True
while repeat:
repeat = False
for i in range(0,len(l)-1):
if frozenset([l[i],l[i+1]]) in c.inverses():
l = l[:i] + l[i+2:]
repeat = True
break
return l

# Helper methods for cancelling inverses in
# non-commutative structures.
def cancelCommutative(s):
r = frozenset([])
for (g1,q1) in s:
qNew = q1
for (g2,q2) in s:
if frozenset([g1,g2]) in c.inverses():
qNew = max(0, q1-q2)
if qNew > 0:
r = r.union({(g1, qNew)})
return r

# Free magmas.
# Part (a).
if not c.associative() and not c.commutative() and\
c.identity() == None and len(c.inverses()) == 0:

# We use lists because both order and hierarchization
# matter.
return constructor((x.elem,y.elem))

# Commutative magmas.
# Part (b).
if not c.associative() and c.commutative() and\
len(c.inverses()) == 0:

# We use sets because order should not matter,
# but they are nested since hierarchization
# still matters.
return constructor(frozenset([x.elem,y.elem]))

# Free semigroups, free monoids, and free groups.
# Parts (c), (e), and (f).
if c.associative() and not c.commutative():

# If either argument is the identity,
# simply return the other argument.
# This only applies to monoids.
if x.elem == c.identity(): return y
if y.elem == c.identity(): return x

# We turn both argument representations into lists
# so that we can operate on generators as single-item
# lists.
x = [x.elem] if not type(x.elem) is list else x.elem
y = [y.elem] if not type(y.elem) is list else y.elem

# We use list concatenation, which is associative.
result = x + y

# If inverses exist, we cancel as necessary.
result = cancelNonCommutative(result)

if len(result) == 0:
result = c.identity()

# If the resulting list has length 1, then use the alternate
# representation of the group element as just the element itself
# instead of a singleton list.
if isinstance(result, list) and len(result) == 1:
result = result

return constructor(result)

# Commutative semigroups, commutative monoids, and commutative groups.
# Parts (d), (e), and (f).
if c.associative() and c.commutative():

# If either argument is the identity,
# simply return the other argument.
# This only applies to monoids.
if x.elem == c.identity(): return y
if y.elem == c.identity(): return x

# We use a relation mapping generators to counts
# (which is just a set of pairs).
x = [(x.elem,1)] if not type(x.elem) is frozenset else x.elem
y = [(y.elem,1)] if not type(y.elem) is frozenset else y.elem

# Collect all the generators found in "x" and "y".
gs = set([g for (g,q) in x] + [g for (g,q) in y])

def lookup(g,x):
d = dict(x)
if g in d: return d[g]
return 0

# Add up the generator counts in "x" and "y" and
# return the resulting relation.
result = {(g, lookup(g,x) + lookup(g,y)) for g in gs}
result = {(g,q) for (g,q) in result if q > 0}

# If inverses exist, we cancel as necessary.
result = cancelCommutative(result)

if len(result) == 0:
result = c.identity()

# If the resulting multiset has cardinality one, then use the
# alternate representation of the group element as just the element
# itself instead of a singleton multiset.
if isinstance(result, frozenset) and len(result) == 1:
element, count = list(result)
if count == 1:
result = element

return constructor(result)

return None```
Additional test cases are provided below.
```class M(AlgebraicStructure):
def generators(self):  return {'A','B','C','D','E'}

M('A') + M('B') == M('B') + M('A') # False.
M('A') + M('C') + M('B') == M('A') + M('B') + M('B') # False.
M('A') + (M('B') + M('C')) == M('A') + (M('B') + M('C')) # True.

class CM(AlgebraicStructure):
def generators(self):  return {'A','B','C'}
def commutative(self): return True

CM('A') + CM('B') == CM('B') + CM('A') # True.
(CM('A') + CM('C')) + CM('B') == CM('B') + (CM('C') + CM('A')) # True.
(CM('A') + CM('B')) + CM('C') == CM('A') + (CM('B') + CM('C')) # False.

class S(AlgebraicStructure):
def generators(self):  return {1,2,3}
def associative(self): return True

(S(1) + S(2)) + S(3) == S(1) + (S(2) + S(3)) # True.
S(2) + S(1) + S(3) == S(3) + S(1) + S(2) # False.

class CS(AlgebraicStructure):
def generators(self):  return {1,2,3}
def associative(self): return True
def commutative(self): return True

(CS(1) + CS(2)) + CS(3) == CS(1) + (CS(2) + CS(3)) # True.
CS(2) + CS(1) + CS(3) == CS(3) + CS(1) + CS(2) # True.

class N(AlgebraicStructure):
def generators(self):  return {1,2,3}
def associative(self): return True
def identity(self):    return 1

(N(3) + N(2)) + N(3) == N(3) + (N(2) + N(3)) # True.
N(2) + N(1) + N(3) == N(3) + N(1) + N(2) # False.
N(1) + N(2) == N(2) + N(1) == N(2) # True.

class CG(AlgebraicStructure):
def generators(self):  return {-1,0,1}
def associative(self): return True
def commutative(self): return True
def identity(self):    return 0
def inverses(self):    return frozenset([frozenset([-1,1]), frozenset([0,0])])

CG(-1) + CG(1) == CG(0) # True.
CG(1) + CG(1) + CG(-1) + CG(-1) + CG(1) == CG(0) + CG(1) # True.
CG(-1) + CG(1) == CG(1) + CG(1) # False.```
3. Implement a new member method `enumerate()` for the `AlgebraicStructure` class. This method should take a single positive integer argument `n`, and should return a set of all the elements in the algebraic structure the representations of which contain n or fewer generators. See the definition of closure for one approach that can be used to implement this method.
```    # Any approach for accessing the subclass that works is
# acceptable. Here, we assume that ".generate()" is always
# invoked on an object of the subclass.
def enumerate(self, n):
def remove_duplicates(l):
"""Inefficiently returns a new list which contains the elements of
`l` with duplicates removed.

If `l` is a set of hashable objects, use ``set(l)`` instead. This
is primarily intended for lists of unhashable objects, like other
lists.

"""
result = []
for x in l:
if x not in result:
result.append(x)
return result
s = []
if n == 1:
for g in self.generators():
s.append(self.__class__(g))
else:
for i in range(1,n):
for x in self.enumerate(i):
for y in self.enumerate(n - i):
s.append(x + y)
return remove_duplicates(s)```
4. In this problem, you will implement methods for splitting an individual element from an algebraic structure (i.e., an object) into multiple parts that can later be reassembled back together to obtain an equivalent object.
1. Implement a method `split()` for the `AlgebraicStructure` class that takes a single argument, a positive integer `n` (note that the definition will also have self as the first argument). This method should return a list; each entry in the list should be an ordered pair `(a,e)` such that `e` is an element in the algebraic structure that contains at most `n` generators, and `a` is an annotation for rebuilding the split-up element. You will need to decide what information, and how much of it, `a` must contain to solve part (b) below. For example, if the element is from a commutative semigroup (defined as a class `CS`) such that elements are represented using sets of generators, you may find that you do not need to store any information in `a` to reconstruct the object. Note the corrected example output below..
```x = CS('a') + CS('b') + CS('c') + CS('d') + CS('e')

# Evaluates to [(None, CS('a') + CS('b')), (None, CS('c') + CS('e')), (None, CS('d'))]
x.split(2)

# Evaluates to "True".
join(x.split(2)) == x```
2. Implement a static method `join()` for the `AlgebraicStructure` class that takes a single argument, a list of pairs of the form `(a,e)`, and restores the original element that was split using `split()`. In other words, we should have for any element `x` that `M.join(x.split(n, p))` is equivalent to `x` for any positive `n`.

You may not assume that the list given as input to `join()` has its elements in the same order as the list returned by `split()`.

Your `join()` implementation should be as efficient as possible given the properties of a particular algebraic structure.

• A split-up element of a commutative semigroup should be reassembled in linear time (in terms of the number of generators).
• A split-up element of a magma should be reassembled in at most quadratic time (in terms of the number of generators). Is it possible to reassemble the element in time O(n log n)?