Assignment #5: Algebraic Structures and Permutations (back to full lecture notes)

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
     
        def __add__(x, y):
     
            # 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[0]
     
                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)[0]
                    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)?