# Generating uniform permutations by a particular method

Let $A$ be a uniformly random permutation of the numbers $\{1,2,\cdots,n\}$. I want to generate a uniformly random permutation from $A$ on the numbers $\{1,2,\cdots,n,n+1,\cdots,n+m\}$. In other words, first I generate $A$ uniformly randomly. Then, taking that $A$, I want to generate $B$ such that final result is uniformly random.

I need to do it as follows: I first generate $A$ and then using an extra $m$ continuous-uniform random variables $X_i$ on the continuous interval $[0,n+m]$, append them at the end of $A$, and then rewrite everything in terms of their relative order.

Example: $n=3$, $m=2$. I generate $A=(2,1,3)$. I generate the two elements $X_1=1.1,X_2=2.6$. Appending this to the end of $A$: $(2,1,3,1.1,2.6)$ and now rewriting in terms of relative order $B=(3,1,5,2,4)$.

Unfortunately I'm not convinced that the final result really is a uniform permutation on $\{1,2,\cdots,n+m\}$. Is there a way to prove or modify it to make it work?

Note: this procedure absolutely has to incorporate the following:

1) Taking a uniformly random A

2) Somehow generating m extra elements $X_i$

3) Appending $X_i$ to the end of $A$.

4) Rewrite in relative order

so really step (2) is the only freedom I have.

You're right, this will not yield a uniform distribution for $m\gt1$. The probability for two given elements to be adjacent in a random order is roughly $\frac2n$ (since each element has roughly $2$ neighbours), whereas in your algorithm for $m=2$ the two additional elements have roughly $\frac1n$ probability of ending up adjacent.
You can't fix this by transforming the $X_i$ individually; as long as they're independent they can't have the right distribution. To modify the algorithm, you could add the additional elements one at a time, $m$ times $1$ instead of $m$ in $1$ go; or you could make the $X_i$ dependent, with joint distribution as required to make the distribution of the resulting permutation come out right. I'm not sure whether either of these options is allowed under your rules.