Getting permutations of independent sequences with uniform probability

Question

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)?

Answer 1

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

2. 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.)

Answer 2

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.

Answer 3

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)$.