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

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.

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

• Yes, it's my solution (except that I assign the $ABC$ all at once). Commented May 22, 2019 at 11:45
• Ah, well. Great minds, and all that. :) Commented May 22, 2019 at 12:09

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