# OK to post homework
# Robert Dougherty-Bliss
# 2021-02-04
# Assignment 5

read "C5.txt":

# 1.

PermuG := proc(n)
    if n = 0 then
        return [[]]:
    fi:

    prev := PermuG(n - 1):

    res := []:
    for k from 1 to nops(prev) do
        pi := prev[k]:
        if k mod 2 = 1 then
            # Insert from right-to-left.
            for j from 1 to n do
                new := [op(pi[..-j]), n, op(pi[-j+1..])]:
                res := [op(res), new]:
            od:
        else
            # Insert from left-to-right.
            for j from 1 to n do
                new := [op(pi[..j-1]), n, op(pi[j..])]:
                res := [op(res), new]:
            od:
        fi:
    od:

    res:
end:

# 2.

# Bah, humbug...there's snow outside!

# 3.

MyRandPermA := proc(n)
    # What's the probability that a random permutation of [n] begins with j?
    # It is exactly (n - 1)! / n! = 1 / n. So, pick some j at random, start
    # with that, pick an (n - 1)-permutation at random, and relabel it
    # correctly.

    if n = 0 then
        return []
    fi:

    start := rand(1..n)():
    prev := MyRandPermA(n - 1):
    prev := Expa(prev, [seq(1..start-1), seq(start+1..n)]):

    [start, op(prev)]:
end:

MyRandPermI := proc(n)
    if n = 0 then
        return []
    fi:

    prev := MyRandPermI(n - 1):

    choice := rand(1..n)():

    [op(prev[1..choice-1]), n, op(prev[choice..])]:
end:

with(CodeTools[Profiling]):
with(combinat):

Profile(MyRandPermI):
Profile(MyRandPermA):
Profile(randperm):

MyRandPermI(1500):
MyRandPermA(1500):
randperm(1500):

PrintProfiles(MyRandPermI):
PrintProfiles(MyRandPermA):
PrintProfiles(randperm):

# randperm is nearly instantaneous!

# 4.

ContainsPattern := proc(pi, L)
    for ks in choose(nops(pi), nops(L)) do
        if Redu([seq(pi[k], k in ks)]) = L then
            return true:
        fi:
    od:

    return false:
end:

NoABC := proc(n)
    select(pi -> not ContainsPattern(pi, [1, 2, 3]), PermuG(n)):
end:

# These are enumerated by the Catalan numbers, A108!