A permutation avoiding a consecutive pattern $\underline{123}$ is permutation
$\pi = \pi\_1 \pi\_2 \ldots \pi\_n$ with the property that there does not exists $i \in [1, n-2]$
such that $\pi\_i < \pi\_{i+1} < \pi\_{i+2}$.
Example: $53241$ is $\underline{123}$-avoiding; while $314562$ is not $\underline{123}$ avoiding, as it contains $145$.


Let $a\_n$ be the number of $\underline{123}$ avoiding permutations,
it is known, [in corresponding OEIS entry A049774](http://oeis.org/A049774), that
$$ \frac{a\_n}{n!} \sim e^{\frac{\pi}{3\sqrt{3}}} \left(\frac{3\sqrt{3}}{{2\pi}}\right)^{n+1}.$$


So, the simple rejection sampling is inefficient even for moderate values of $n$.
How does one generate such permutations uniformly at random?


I'm aware of [Boltzmann sampling](https://hal.archives-ouvertes.fr/hal-00411110/document).
But maybe you are aware of more simple and/or faster algorithms as in the [case of alternating permutations](https://mathoverflow.net/questions/14863/random-alternating-permutations).



Random permutations without double rises (avoiding consecutive pattern $\underline{123}$)
I have a sampling algorithm for you written in sage / python.


Instead of $\underline{123}$ avoiding permutations of length $n$ I consider words $w\_1 w\_2 \dots w\_n$ satisfying the following properties:


* $0\le w\_k \le n-k$
* the word is weakly $\underline{123}$ avoiding, which means there is no index $i\in [1,n-2]$ such that $w\_i\le w\_{i+1} \le w\_{i+2}$.


I call these words $\underline{123}$ avoiding indexwords.
They are in bijection with $\underline{123}$ avoiding permutations using the following bijection: Let $S=\{1,2,\dots,n\}$ then for a given indexword $w\_1 w\_2 \dots w\_n$ we define $\pi\_i = w\_i\text{-th smallest entry of } S\setminus\{\pi\_1,\dots,\pi\_{i-1}\}$, where I start indexing the entries of the set with $0$.
Put differently: If we keep track of the unused letters to build up the permutation in an ordered list, then $\pi\_i$ is precisely the $w\_i\text{-th}$ entry in that list (explaining my name for these words).


These words will simplify the following algorithm for random uniform sampling.
The algorithm comes in two steps: First count the number of $\underline{123}$ avoiding indexwords with a given prefix. Then create a random word iteratively by appending letters to the already constructed word using certain probabilities using the precomputed values.


For this let $\alpha\_n^{w\_1 w\_2 \dots w\_l}$ be the number of $\underline{123}$ avoiding indexwords of length $n$ starting with $w\_1 w\_2 \dots w\_l$.
For calculating these values, we have two rules:
Let $w\_1 w\_2 \dots w\_l$ be weakly $\underline{123}$ avoiding, then


1. Expansion rule
$$
\alpha\_n^{w\_1 w\_2 \dots w\_l} = \sum\_{0\le x\le n-l-1 \text{ and } \neg(w\_{l-1}\le w\_l\le x)} \alpha\_n^{w\_1 w\_2 \dots w\_l x}
$$
2. Reduction rule
$$ 
\alpha\_n^{w\_1 w\_2 \dots w\_l} = \alpha\_{n-l+2}^{w\_{l-1}w\_l}
$$
3. Start cases
$$
\alpha\_2^{00}=\alpha\_2^{10}=1
$$


Combining the rules we obtain
$$
\alpha\_n^{xy}=\sum\_{0\le z\le n-3 \text{ and } \neg(x\le y\le z)}\alpha\_{n-1}^{yz}
$$


Note that you can obtain $a\_n$ by summing $\alpha\_n^{xy}$ over all pairs $(x,y)\in [0,n-1]\times [0,n-2]$


Now for the sampling part.
Randomly choose a pair $(x,y)\in [0,n-1]\times [0,n-2]$ with probability $\frac{\alpha\_n^{xy}}{a\_n}$.
Assume now, we have already created a sequence $w\_1 \dots w\_l$ with $l<n$, we append an appendable letter $x\in [0,n-l-1]$ with probabilty
$\frac{\alpha\_{n+1-l}^{w\_l x}}{\alpha\_{n+2-l}^{w\_{l-1} w\_{l}}}$.
(A letter is appendable, if it does not create the $\underline{123}$ pattern).
Repeat this until you have a $\underline{123}$ avoiding indexword of length $n$.


Here is the sage code:



```
@cached_function
def alpha(n,x,y):
    assert n>1, "n needs to be at least 2"
    if n == 2:
        return 1
    return sum(alpha(n-1,y,z) for z in range(n-2) if not (x<=y<=z))

def random_indexword(n):
    assert n>=2, "Algorithm only works for length n>=2"
    pairs = [(x,y) for x in range(n) for y in range(n-1)]
    P = [alpha(n,x,y) for x,y in pairs]
    s1,s2 = pairs[GeneralDiscreteDistribution(P).get_random_element()]
    indexword = [s1,s2]
    while len(indexword)<n:
        appendable = [x for x in range(n-len(indexword)) if not (indexword[-2] <= indexword[-1] <= x)]
        P = [alpha(n+1-len(indexword), indexword[-1],x) for x in appendable]
        indexword.append(appendable[GeneralDiscreteDistribution(P).get_random_element()])

    return indexword

def indexword_to_permutation(word):
    letters = [i for i in range(1,len(word)+1)]
    p = []
    for i in word:
        p.append(letters[i])
        letters.remove(p[-1])
    return p

# for testing
def is_123_avoiding(perm):
    return not any(perm[i]<perm[i+1]<perm[i+2] for i in range(len(perm)-2))

w = random_indexword(10)
perm = indexword_to_permutation(w)
perm,is_123_avoiding(perm)

```

Edit: Updated typo in bijection between index words and permutations.


