CoCalc -- permutations-tutorial.sagews

Permutations Tutorial for Math 4660

Algebraic Combinatorics Class - Seelinger

⁴⁵⁰ views
ubuntu2204

Permutations

This worksheet is a beginner's tutorial to how to work with permutations in SageMath. This worksheets assumes no prior knowledge of coding in Python or Sage, but seeks to demonstrate primarily by example and does not provide lengthy explanations of concepts. If you are confused or want more detail about a specific concept, feel free to ask questions or to Google the concept.

Some reminders:

Remember that you run code in a "cell" by hitting "Shift" and "Enter" while your cursor is in the shell.
If you put the # character on a line, everything after on that line is ignored. We call this a comment and there are helpful comments placed throughout this worksheet in code boxes.
There are coding exercises throughout this worksheet denoted with bold Exercise at the beginning. You can complete the exercises in a cell below the exercise.
All permutations are given in one-line notation.

Finally, run this code to make sure permutation composition agrees with your class. We want $(\sigma \circ \tau)(i) = \sigma(\tau(i))$ for permutations $\sigma, \tau$ .

Permutations.options(mult='r2l')

You can create permutation objects using one-line notation.

sigma = Permutation([3,1,6,5,7,2,4])
sigma(1), sigma(2), sigma(3), sigma(4), sigma(5), sigma(6), sigma(7)

(3, 1, 6, 5, 7, 2, 4)

Exercise: Create a permutation tau that sends 1 to 3, 2 to 1, 3 to 2, and fixes 4,5,6,7. Then, check that it works correctly.

tau = # Fill this in
tau(1) == 3
tau(2) == 1
tau(3) == 2

You can multiply and invert permutations!

sigmaprime = sigma.inverse()
sigmaprime

[2, 6, 1, 7, 4, 3, 5]

sigma*sigmaprime

[1, 2, 3, 4, 5, 6, 7]

Exercise: What is the inverse permutation to tau above? Write it down and then check your answer!

# Check your answer here

If/Else Statements

In programs, we can control the logic flow using "if/else" statements. Let's try an example. Remember that a permutation $\sigma$ is called an involution if $\sigma = \sigma^{-1}$ .

sigma = Permutation([3,1,6,5,7,2,4])
if sigma == sigma.inverse():
    print("sigma is an involution!")
else:
    print("sigma is not an involution.")

sigma is not an involution.

Exercise: Check if sigma2 defined below is an involution or not using an "if/else" statment. Also, pay attention to how indentation is used in the above example.

Also, notice that in Sage, you check if two things are equal using a double equals sign, ==

sigma2 = Permutation([2,1,4,3,6,5,7])

It is annoying to rewrite the same blocks of code over and over again, so instead we can create functions to reuse code. Functions work like this silly example.

def add_two_numbers(num1, num2):
    print("Adding some numbers!")
    return num1+num2

add_two_numbers(3,5)

Adding some numbers!
8

Exercise: Write a function is_perm_inv to check whether or not a permutation is an involution. Test it on sigma and sigma2.

def is_perm_inv(perm):
    # your code here

# Tests for you to run.
is_perm_inv(sigma)
is_perm_inv(sigma2)

List Comprehensions

In Python, there is a tool called a "list comprehension" that allows you to apply a function to every element in a list. So, if you have some function f and some list L, then [f(a) for a in L] will apply the function to every list element. Let's look at an example

Definition: We say a permutation $\sigma$ has an inversion $(i,j)$ if $i < j$ and $\sigma_i > \sigma_j$ .

Definition: the length of a permutation $\sigma$ is the number of pairs $(i,j)$ such that $i < j$ and $\sigma_i > \sigma_j$ , ie the number of inversions $\sigma$ has.

Then, given a length $\ell$ and a size $n$ , we may wonder how many permutations of size $n$ have length $\ell$ .

# Calculate the length of every permutation of {1,2,3}
[(perm,perm.length()) for perm in Permutations(3)]

[([1, 2, 3], 0), ([1, 3, 2], 1), ([2, 1, 3], 1), ([2, 3, 1], 2), ([3, 1, 2], 2), ([3, 2, 1], 3)]

Lists are an essential data structure in Python, so it is important to know how to manipulate them.

Exercise: Using your is_perm_inv function, create a list using a list comprehension that tells you which permutations of 3 are inversions and which ones are not, similar to the list above.

# Compute which permutations of {1,2,3} are inversions and which are not

We can also combine list comprehensions and if statements like so

# List all permutations of {1,2,3} with length 1.
[perm for perm in Permutations(3) if perm.length() == 1]

[[1, 3, 2], [2, 1, 3]]

This notation is meant to read like an English sentence. That is, this list contains every permutation in Permutations(3) if the length of the permutation is 1. So, the if condition "filters" your list comprehension and only contains the items that satisfy the condition.

Exercise: Write a function called involutions(n) that returns a list of all permutations of $\{1,\ldots,n\}$ that are involutions. Check your result on permutations of $\{1,2,3\}$ and make sure it agrees with what you know mathematically.

def involutions(n):
    # your code here

Definition: The Lehmer code of a permutation $\sigma$ on $\{1,\ldots,n\}$ is a list $(L_1, L_2, \ldots, L_n)$ where $L_i$ is the number of $j>i$ such that $\sigma_j < \sigma_i$ .

In SageMath, you can compute the Lehmer code of a permutation. Furthermore, SageMath provides documentation of built-in functions. If you want to know more about a function, you can type the name of the function followed by a question mark, like in this example below.

# Run this code to get a useful description of how to use Lehmer codes in Sage
perm = Permutation([1,2,3])
perm.to_lehmer_code?

You can also Google "sage Lehmer code" to quickly get a website version of this help page. It is very useful to learn how to read and search the SageMath reference manual so you can figure out how to use functions in Sage.

%md
**Definition**: We say a permutation $\sigma$ has a *descent at position $i$* if $\sigma_i > \sigma_{i+1}$.

For example, $\sigma = (4,2,3,1)$ has descents at $i=1$ and $i=3$.

**Exercise**: Modify the list comprehension below to create a list that shows all permutations of $\{1,2,3,4\}$ that have exactly 1 descent and their Lehmer codes. Do you notice anything interesting about the Lehmer codes of these permutations?

Definition: We say a permutation $\sigma$ has a descent at position $i$ if $\sigma_i > \sigma_{i+1}$ .

For example, $\sigma = (4,2,3,1)$ has descents at $i=1$ and $i=3$ .

Exercise: Modify the list comprehension below to create a list that shows all permutations of $\{1,2,3,4\}$ that have exactly 1 descent and their Lehmer codes. Do you notice anything interesting about the Lehmer codes of these permutations?

# modify this list!
cds = [perm for perm in Permutations(4) if perm.number_of_descents()==1]
cds

You can also view exactly where the descents of a permutation are like so

perm = Permutation([2,1,4,3])
perm.descents()

[1, 3]

In Python, lists are indexed starting at 0. So, this output says the permutation $(2,1,4,3)$ has descents at positions 2 and 4. To see what is happening more concretely, look at the list example below.

L = [1,2,3]
L[0]
L[2]

1
3

So, when we work with lists in Python and Sage, we need to get used to count starting with 0 instead of with 1.

Exercise Examine and run the code below. While this code contains concepts we have not covered yet, see if you can understand what it does. Compare its output to the permutations in the previous exercise.

for perm in Permutations(5):
    desc = perm.descents()
    if perm.number_of_descents() == 1:
        print("Descent at position {}".format(desc[0]+1))
        print(perm.to_lehmer_code())
        print("")

For loops

In Python, you can iterate over items in a list in the order they appear using a for loop. The code in the last exercise used a for loop to print information about each permutation of $\{1,2,3,4,5\}$ that had exactly 1 descent.

for perm in Permutations(3):
    print(perm, perm.length())

([1, 2, 3], 0)
([1, 3, 2], 1)
([2, 1, 3], 1)
([2, 3, 1], 2)
([3, 1, 2], 2)
([3, 2, 1], 3)

For loops can be useful for doing complex operations for each element of a list. For example, we can print out a multiplication table of permutations (although it may not be easy to read).

from __future__ import print_function

#print top row
print(" "*(3*3+2), end='')
for perm in Permutations(3):
    print(perm, end=' ')
print("")
# print dashes to distinguish top row
print("-"*(70))
# print the rest of the forws
for perm in Permutations(3):
    # start each row with first factor
    print("{} |".format(perm), end='')
    # print multiplication table entries for this row
    for perm2 in Permutations(3):
        print(perm*perm2, end=' ')
    # move cursor to the next line
    print("")

Final remarks

In this tutorial, we covered the basics of how to use permutations in SageMath, if/else, list comprehensions, and for loops. However, we have only just scratched the surface! There is much more to learn.

To learn more about the various programming structures in Python, check the control flow section of the Python tutorial
To learn more about what Sage can do with permutations, visit the documentation for the Permutation class

Permutations Tutorial for Math 4660

Permutations

If/Else Statements

List Comprehensions

For loops

Final remarks

Product

Resources

Company