| Hosted by CoCalc | Download
Kernel: SageMath 9.2

Math 157: Intro to Mathematical Software

UC San Diego, Winter 2020

Permutation Patterns

By Hanad Ahmed

Quick Permutation Review:

What is a Permutation?

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:

  • Gambling

  • Cryptography

  • Architecture

  • etc

A permutation of length nn is a reordering of the list [1,2,…,n][1,2,\dots,n]. We will usually write a permutation as π=π1π2…πn \pi = \pi_1\pi_2\dots\pi_n 

perms = Permutations(4)
print(perms)
Standard permutations of 4 
for p in perms:
    print(p)
[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]

Permutations give the number of ways to arrange n numbers and are counted by the factorial n!=n⋅(n−1)…3⋅2⋅1.n! = n\cdot(n-1)\dots 3\cdot 2\cdot 1.

print(P.cardinality())
print(factorial(4))
24 24

Permutations:

To find number of ways to choose r slots out of n total items. number-of-permutations⁡(items,slots)=items!(items−slots)! \operatorname{number-of-permutations}(\mathit{items}, \mathit{slots}) = \frac {\mathit{items}!} {(\mathit{items} - \mathit{slots})!} 

Arrangements( ["c","a","t"], 2 ).list()
[['c', 'a'], ['c', 't'], ['a', 'c'], ['a', 't'], ['t', 'c'], ['t', 'a']]
Arrangements(["c","a","t"],2).cardinality()
6

Permutation Patterns: (Its about to get real!)

440px-Permutation_generation_algorithms.svg

What is Permutation Pattern?

A permutation pattern is a sub permutation of a seperate pattern. Pattern permutations are based on two main concepts: containment and avoidance

Pattern Containment:

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)x = (1432) and y=(12)y =(12). Notice xx contains a pattern in yy because as we can see the order of xx is ascending on the first two digits of the permutation and the same is for yy. So we can choose any subsequence in xx such as (14)(14) and it contains the permutation (12)(12).

Permutation Patterns can be tricky to notice. Lets use sage to help.

 Permutation([1,4,3,2]).has_pattern([1,2])
True
Permutation([1,4,3,2]).pattern_positions([1,2])
[[0, 1], [0, 2], [0, 3]]

Notice that there is more than one subsequence xx that contains yy as a pattern

Pattern Avoidance

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])
True

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

***** Participation Check ***************************

Find a permutation that contains the pattern (231)(231). Answer below

Does the permutation (4,2,3,1)(4, 2, 3, 1) contains or avoid the permutation (2,1)? If contains. how many patterns? Answer below

*********************************************************

Stack sortability of permutations:

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:

  • Initialize an empty stack

  • For each input value x:

    • While the stack is nonempty and x is larger than the top item on the stack, pop the stack to the output

    • Push x onto the stack

  • While the stack is nonempty, pop it to the output

dishes

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])
False
Permutation([4, 3, 2, 1]).avoids([2,3,1])
True

Exercise 1: Catalan Numbers

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=1n+1(2nn)=(2n)!(n+1)! n!=∏k=2nn+kkfor n≥0. C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} = \prod\limits_{k=2}^{n}\frac{n+k}{k} \qquad\text{for }n\ge 0.

Catalan6

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=1    and    Cn=∑k=0n−1CkCn−1−k,n≥2 C_0 = 1 \; \; and \; \; C_n = \sum_{k = 0}^{n-1} C_k C_{n-1-k} , {n} \geq 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)?

Exercise 1: Catalan Numbers (SOLUTION)

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=1n+1(2nn)=(2n)!(n+1)! n!=∏k=2nn+kkfor n≥0. C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} = \prod\limits_{k=2}^{n}\frac{n+k}{k} \qquad\text{for }n\ge 0.

Catalan6

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=1    and    Cn=∑k=0n−1CkCn−1−k,n≥2 C_0 = 1 \; \; and \; \; C_n = \sum_{k = 0}^{n-1} C_k C_{n-1-k} , {n} \geq 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))
1 1 2 5 14

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)
[1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]

Exercise 2: Stack Sortability

stack_1_32

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):

  • Initialize an empty stack

  • For each input value x:

    • While the stack is nonempty and x is larger than the top item on the stack, pop the stack to the output

    • Push x onto the stack

  • While the stack is nonempty, pop it to the output

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

Exercise 2: Stack Sortability (SOLUTION)

stack_1_32

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):

  • Initialize an empty stack

  • For each input value x:

    • While the stack is nonempty and x is larger than the top item on the stack, pop the stack to the output

    • Push x onto the stack

  • While the stack is nonempty, pop it to the output

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))
deque([1, 2, 3]) 
print(sort(perm) == perm.sort())
False