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.
[2,1,0]
. For example,
given some ordered list of elements such as ['a','b','c']
, after the permutation [2,1,0]
is applied:
'a'
with index 0
in ['a','b','c']
should move to the location with
index 2
in the result;
'b'
with index 1
in ['a','b','c']
should move to the location with
index 1
in the result;
'c'
with index 2
in ['a','b','c']
should move to the location with
index 0
.
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'].
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)
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).
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]}.
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)) == pSee 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))
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 NoneIt 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 TrueComplete 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()
.
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 NoneAdditional 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.
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)
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
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.