CoCalc Public FilesFinalProjects / Hanad'sFinalProject.ipynbOpen with one click!A permutation is a mathematical technique that determines the number of possible arrangements in a set when the order of the arrangements matters.
Permutations are used in so many things such as:
A permutation of length n is a reordering of the list [1,2,…,n]. We will usually write a permutation as π=π1π2…πn
perms = Permutations(4) print(perms)
for p in perms: print(p)
Permutations give the number of ways to arrange n numbers and are counted by the factorial n!=n⋅(n−1)…3⋅2⋅1.
print(P.cardinality()) print(factorial(4))
To find number of ways to choose r slots out of n total items.
number-of-permutations(items,slots)=(items−slots)!items!
Arrangements( ["c","a","t"], 2 ).list()
Arrangements(["c","a","t"],2).cardinality()
A permutation pattern is a sub permutation of a seperate pattern. Pattern permutations are based on two main concepts: containment and avoidance
If π and σ are two permutations, then π is said to CONTAIN σ as a pattern if some subsequence of the digits of π has the same relative order as all of the digits of σ. Permutation Patterns focus on the relationship of two permutations rather than the actual numbers of the two.
For example:
let x=(1432) and y=(12). Notice x contains a pattern in y because as we can see the order of x is ascending on the first two digits of the permutation and the same is for y. So we can choose any subsequence in x such as (14) and it contains the permutation (12).
Permutation Patterns can be tricky to notice. Lets use sage to help.
Permutation([1,4,3,2]).has_pattern([1,2])
Permutation([1,4,3,2]).pattern_positions([1,2])
Notice that there is more than one subsequence x that contains y as a pattern
Pattern avoidance is the angalous of pattern containment. If a permutation π does not contain a pattern σ, then π is said to avoid σ.
For example:
The permutation π = (4321) avoids the permutation σ = (12) because π has no ascending subsequence.
Permutation([4,3,2,1]).avoids([1,2])
This will give us an error because no pattern exists
Permutation([4,3,2,1]).pattern_postions([1,2])
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
<ipython-input-15-62217f902c2a> in <module>
----> 1 Permutation([Integer(4),Integer(3),Integer(2),Integer(1)]).pattern_postions([Integer(1),Integer(2)])
/ext/sage/sage-9.2/local/lib/python3.8/site-packages/sage/structure/element.pyx in sage.structure.element.Element.__getattr__ (build/cythonized/sage/structure/element.c:4703)()
491 AttributeError: 'LeftZeroSemigroup_with_category.element_class' object has no attribute 'blah_blah'
492 """
--> 493 return self.getattr_from_category(name)
494
495 cdef getattr_from_category(self, name):
/ext/sage/sage-9.2/local/lib/python3.8/site-packages/sage/structure/element.pyx in sage.structure.element.Element.getattr_from_category (build/cythonized/sage/structure/element.c:4815)()
504 else:
505 cls = P._abstract_element_class
--> 506 return getattr_from_other_class(self, cls, name)
507
508 def __dir__(self):
/ext/sage/sage-9.2/local/lib/python3.8/site-packages/sage/cpython/getattr.pyx in sage.cpython.getattr.getattr_from_other_class (build/cythonized/sage/cpython/getattr.c:2553)()
365 dummy_error_message.cls = type(self)
366 dummy_error_message.name = name
--> 367 raise AttributeError(dummy_error_message)
368 cdef PyObject* attr = instance_getattr(cls, name)
369 if attr is NULL:
AttributeError: 'StandardPermutations_all_with_category.element_class' object has no attribute 'pattern_postions'
Take two minutes and try to answer these questions
Find a permutation that contains the pattern (231). Answer below
Does the permutation (4,2,3,1) contains or avoid the permutation (2,1)? If contains. how many patterns? Answer below
A stack is one of the most important data structures in computer science. The order of the stack is similar to a stack of dishes, where the last thing put in is the first thing taken out.
The algorithm to sort a stack is:
Stack-sortable permutation is a permutation whose elements may be sorted by an algorithm whose internal storage is limited to a single stack data structure. This is significant because stack storing doesnt depend on the value the input but the relative order to other inputs. This is where permutation patterns come in play. The algorithm to correctly sort a stack is the permutation that avoids the permutation 231.
Computer scientist Donald Knuth concluded that if the algorithm fails to sort an input using (231), then that input cannot be sorted with a single stack.
For example:
Input permutation (123) into the sorting algorithm. all three numbers are pushed into the stack, then popped in the order (321).
But if you try to input the permutation (231) into the algorithm it fails. The algorithm first pushes 2, and pops it when it sees the larger input value 3, causing 2 to be output before 1 rather than after it.
Lets show this on sage
Permutation([1, 3, 4, 2]).avoids([2,3,1])
Permutation([4, 3, 2, 1]).avoids([2,3,1])
Catalan number is a sequence of numbers that commonly occurs in enumeration/counting problems.
The ''n''th Catalan number is given directly in terms of binomial coefficients by Cn=n+11(n2n)=(n+1)!n!(2n)!=k=2∏nkn+kfor n≥0.
Cn is the number of permutations of {1, ..., n} that avoid the permutation pattern 123 (or, alternatively, any of the other patterns of length 3); that is, the number of permutations with no three-term increasing subsequence.
Similar to fibonacci sequence. The Catalan numbers satisfy the recurrence relations: C0=1andCn=k=0∑n−1CkCn−1−k,n≥2
a.) Find the nth catalan number
def catalan(n):
b.) Print the first 5 catalan numbers. look up the catalan numbers to check answers
c.) What are the valid permutations for catalan(3)?
Catalan number is a sequence of numbers that commonly occurs in enumeration/counting problems.
The ''n''th Catalan number is given directly in terms of binomial coefficients by Cn=n+11(n2n)=(n+1)!n!(2n)!=k=2∏nkn+kfor n≥0.
Cn is the number of permutations of {1, ..., n} that avoid the permutation pattern 123 (or, alternatively, any of the other patterns of length 3); that is, the number of permutations with no three-term increasing subsequence.
Similar to fibonicii sequence. The Catalan numbers satisfy the recurrence relations: C0=1andCn=k=0∑n−1CkCn−1−k,n≥2
a.) Find the nth catalan number
def catalan(n): # Base Case if ((n == 0) or (n == 1)) : return 1 #recursion catNumber = 0 for i in range(n): catNumber += catalan(i) * catalan(n-i-1) return catNumber
b.) Print the first 5 catalan numbers. look up the catalan numbers to check answers
for i in range(5): print(catalan(i))
c.) What are the valid permutations for catalan(3)?
perms = Permutations(3) for i in perms: if(Permutation(i).avoids([1,2,3])): print(i)
Being able to sort a stack of inputs is important in computer science. Lets implement the algorithm to allow us to sort a stack using the algorithm.
def(sort):
a.) create the stack sort algorithm
from collections import deque
def sort(n): stack = deque()
b.) Find a valid permutation to sort using permutation patterns
Being able to sort a stack of inputs is important in computer science. Lets implement the algorithm to allow us to sort a stack using the algorithm.
def(sort):
a.) create the stack sort algorithm
from collections import deque
def sort(n): #start with an empty stack stack = deque() #while the n is not empty while(len(n) != 0): #get the last element in n and remove it last = n[-1] n.pop() #while our stack is not empty and the last element in our stack is greater than last element in n while((len(stack) != 0) and (stack[-1] > last)): #add our last element into n and pop the element n.append(stack[-1]) stack.pop() #add the last element of n to our stack stack.append(last) #when we go through all of n return our stack return stack
b.) Find a valid permutation to sort using permutation patterns
perm = [2, 1, 3] Permutation(perm).avoids([2,3,1]) print(sort(perm))
print(sort(perm) == perm.sort())