Getting permutations of independent sequences with uniform probability Let's say we have $n=3$ sequences noted $A, B, C$ each composed of $m=3$ ordered operations such that $A = (A_0, A_1, A_2)$, $B = (B_0, B_1, B_2)$ and $C = (C_0, C_1, C_2)$.
I am searching for an algorithm that returns a sequence of 9 operations with a random ordering but still preserving the order of each sequence (e.g. $(A_0, B_0, A_1, C_0, C_1, A_2, B_1, C_2, B_2)$). This gives exactly $\frac{(nm)!}{(m!)^n} = \frac{9!}{(3!)^3} = 1680$ possibles sequences.
The only solution I've found so far can be summarized by the following pseudo-code:

To put it in a nutshell, it randomly picks a sequence at each step and add its current operation to the output sequence.
However, a drawback of this method is that all output sequences do not occur with the same probability. For instance $(A_0, A_1, A_2, B_0, B_1, B_2, C_0, C_1, C_2)$ occurs with probability $\left(\frac{1}{3}\right)^3 \times \left(\frac{1}{2}\right)^3 = \frac{1}{216}$ while $(A_0, A_1, B_0, B_1, C_0, C_1, A_2, B_2, C_2)$ occurs with probability $\left(\frac{1}{3}\right)^7 \times \frac{1}{2} = \frac{1}{4374}$.
What kind of algorithm could I use to build output sequences that occur with a uniform probability (i.e. $\frac{1}{1680}$ in this specific toy example)?
 A: Ignore the order constraint first and generate a random combined sequence of operations. Then for each of the $n$ individual sequences, keep the positions its $m$ operations occupy in the combined sequence, but sort those operations to satisfy the order constraint.
Each valid combined ordering is the result of sorting any one of $(m!)^n$ raw orderings, so the valid orderings have a uniform probability of being produced.
A: Keep track of how many symbols from each sequence remain to be chosen.  Suppose, at step $t$, there are $L_i$ symbols from sequence $i$ not yet used.  Pick the next symbol from sequence $i$ with probability $L_i/\sum_k L_k = L_i/(nm-t)$.
A: *

*Generate a sequence of the form 
$$
(A, B, A, A, B, C, B, C, C)
$$
i.e., with three As, three Bs, three Cs. 

*Then relabel those in each sequence in order, i.e.
$$
(A1, B1, A2, A3, B2, C1, B3, C2, C3)
$$
How to do step 1 in detail: Pick three distinct numbers uniformly from $1...9$, say, $1, 3, 4$. (To do this, pick a first one unif. randomly; then pick a second, unif. randomly, until you get one that's different from the first. Then pick a third, unif. randomly, until you get one distinct from the first two. With very high probability, this will happen fast. Alternative approach below.) Put A's in these slots:
$$
(A, ?, A, A, ?, ?, ?, ?, ?)
$$
Now pick three numbers uniformly from $1..6$, say $1, 2, 4$, and replace the 1st, 2nd, and 4th question-marks with Bs:
$$
(A, B,A, A, B, ?, B, ?, ?)
$$
Replace the last 3 question marks with Cs. 

Alternative (simpler) approach, assuming you've got an algorithm to generate permutations uniformly randomly: pick a random permutation of $1...9$, say 
$$
(3, 4, 1, 2,5, 7, 6, 8, 9)
$$
Replace $1, 2, 3$ with $A1, A2, A3$, but ordered left-to-right; replace $4, 5, 6$ with $B1, B2, B3$ similarly ordered; replace $7, 8, 9$ with $C_1, C2, C3$ similarly ordered. 
I.e., you walk through your sequence looking for the numbers $1, 2, 3$; when you find the first one, you replace it with $A1$; when you find the second, you replace it with $A2$, and so on. 
(I believe that this is @ParclyTaxel's solution, but I'm not certain, as I could not completely make sense of that one.)
