Let $S_n$ be the set of all permutations of $\{1,2,...,n\}$ and $$S_{k,n}=\left\{\sigma=(\sigma(1),...,\sigma(n)) \in \mathcal{S}_n : \sum \limits_{j=1}^{n}j\sigma(j)\geq k\right\}$$ for a $k\in \mathbb{N}$ such that $S_{k,n}\neq \emptyset$.
I want to construct an irreducible Markov chain on $S_{k,n}$ which has a uniform distribution on $S_{k,n}$ as a stationary distribution in order to use it for simulation.
What are good methods to do so?
To elaborate my comment further:
Metropolis-Hastings with finite state space
Let $E$ be a finite state space with the usual $\sigma$-algebra. Since $E$ is finite we can identify probability measures on $E$ with non-negative vectors that sum to 1 and probability kernels on $E$ with non-negative matrices whose columns sum to 1.
Let $q$ be the reference probability kernel on $E$ and $\pi$ the positive target distribution. Then the Metropolis-Hastings kernel is defined by \begin{equation} p(x,y) = \begin{cases} q (x,y) \min \big \{ \frac{\pi (y) q(y , x)}{ \pi (x) q(x, y)}, 1 \big \}, \ \text{if} \ q(x,y) \neq 0 \ \text{and} \ x \neq y,\\ 0, \ \text{if} \ q(x,y) =0 \ \text{and} \ x \neq y,\\ 1 - \sum_{z \neq x} p(x,z) \ \text{if} \ x=y, \end{cases} \end{equation} for $x,y \in E$. The intuitive meaning is that $p(x,y)$ is the probability to transition from the state $x$ to the state $y$. Also note that $\pi$ is a stationary distribution of $p$ because $p$ and $\pi$ satisfy the detailed balance condition.
Application to the uniform distribution on $S_n$
To apply this construction to the case of interest let $E=S_n$ and $\pi$ be the uniform distribution on $E$. Define the reference kernel $q$ on $E$ by $$q(x,y) = \begin{cases} 1/L, \quad \text{if there exist a transposition $T$ so that $y=Tx$}\\ 0, \quad \text{else}, \end{cases}$$ where $L = \frac{n^2}{2}$ is the number of different transpositions (counting the identity as a transposition). Now $p$ is irreducible and aperiodic and so the distribution of any Markov chain with state space $E$ and transition kernel $p$ will converge to $\pi$.
Then all that is left is to construct a Markov-Chain using the computer that has the Metropolis-Hastings kernel as a transition kernel. Note that this Markov-Chain will be trivial in a certain sense, because $\pi$ is the uniform distribution.
We can then use that Markov-Chain to sample from $S_{n,k}$ by throwing away the samples that do not meet the condition or slightly modify the existing solution for $S_n$.