Generating Constrained Random Distributions

Question

I am trying to help another StackExchange user. We are attempting to fill a 6x6 matrix with 12 A's, 12 B's, and 12 C's subject to the constraint that each row contains 2 A, 2B and 2 C and each column also contains 2 As, 2 Bs, and 2Cs.

We would like to do this in a random fashion. I came up with one distribution quite easily:

Examining this, it occurred to me that I could interchange the first two columns and the result would still meet the constraint. In fact I could interchange any two columns chosen at random and meet the constraint.

The same is true for rows.(I guess this is similar to Magic Squares.)

My question is: Can I get any solution by performing a set of these interchanges. That is, are there solutions meeting the constraints that cannot be reached by performing row and column interchanges?

If you feel that this is not a valid Mathematics question, I will delete it. If I have mis-tagged this question, please let me know.

Answer 1

Firstly, the reason why exchanging rows and columns still maintains the condition we desire is because the condition does not care for where the letters are, only the number of occurrences of each letter. Swapping rows and columns clearly does not change that, so any row or column exchanges are okay.

However, no matter how you switch the rows and the columns, all of the rows and columns are going to be of the same "rotation group". What I mean by that is this: If you rotate the letters of any row and get a different row, those two rows are part of the same group of rotations. So $ABC$ can be rotated to get $BCA$ and $CAB$.

Let's rewrite this matrix using $1$, $2$, and $3$ to demonstrate this. From left to right, we have the original matrix, the row rotations, and the column rotations. $$A \ B \ C \ A \ B \ C \ \ \ \ \ \ \ \ \ 1 \ 2 \ 3 \ 1 \ 2 \ 3 \ \ \ \ \ \ \ \ \ 1 \ 1 \ 1 \ 1 \ 1 \ 1\\ A \ B \ C \ A \ B \ C \ \ \ \ \ \ \ \ \ 1 \ 2 \ 3 \ 1 \ 2 \ 3 \ \ \ \ \ \ \ \ \ 1 \ 1 \ 1 \ 1 \ 1 \ 1\\ B \ C \ A \ B \ C \ A \ \ \ \ \ \ \ \ \ 1 \ 2 \ 3 \ 1 \ 2 \ 3 \ \ \ \ \ \ \ \ \ 2 \ 2 \ 2 \ 2 \ 2 \ 2\\ B \ C \ A \ B \ C \ A \ \ \ \ \ \ \ \ \ 1 \ 2 \ 3 \ 1 \ 2 \ 3 \ \ \ \ \ \ \ \ \ 2 \ 2 \ 2 \ 2 \ 2 \ 2\\ C \ A \ B \ C \ A \ B \ \ \ \ \ \ \ \ \ 1 \ 2 \ 3 \ 1 \ 2 \ 3 \ \ \ \ \ \ \ \ \ 3 \ 3 \ 3 \ 3 \ 3 \ 3\\ C \ A \ B \ C \ A \ B \ \ \ \ \ \ \ \ \ 1 \ 2 \ 3 \ 1 \ 2 \ 3 \ \ \ \ \ \ \ \ \ 3 \ 3 \ 3 \ 3 \ 3 \ 3$$

No matter how you switch the rows and columns, the rotations are going to be the same across all rows/columns: $$C \ B \ A \ C \ A \ B \ \ \ \ \ \ \ \ \ 1 \ 2 \ 3 \ 1 \ 3 \ 2 \ \ \ \ \ \ \ \ \ 1 \ 1 \ 1 \ 1 \ 1 \ 1\\ B \ A \ C \ B \ C \ A \ \ \ \ \ \ \ \ \ 1 \ 2 \ 3 \ 1 \ 3 \ 2 \ \ \ \ \ \ \ \ \ 2 \ 2 \ 2 \ 2 \ 2 \ 2\\ B \ A \ C \ B \ C \ A \ \ \ \ \ \ \ \ \ 1 \ 2 \ 3 \ 1 \ 3 \ 2 \ \ \ \ \ \ \ \ \ 2 \ 2 \ 2 \ 2 \ 2 \ 2\\ C \ B \ A \ C \ A \ B \ \ \ \ \ \ \ \ \ 1 \ 2 \ 3 \ 1 \ 3 \ 2 \ \ \ \ \ \ \ \ \ 1 \ 1 \ 1 \ 1 \ 1 \ 1\\ A \ C \ B \ A \ B \ C \ \ \ \ \ \ \ \ \ 1 \ 2 \ 3 \ 1 \ 3 \ 2 \ \ \ \ \ \ \ \ \ 3 \ 3 \ 3 \ 3 \ 3 \ 3\\ A \ C \ B \ A \ B \ C \ \ \ \ \ \ \ \ \ 1 \ 2 \ 3 \ 1 \ 3 \ 2 \ \ \ \ \ \ \ \ \ 3 \ 3 \ 3 \ 3 \ 3 \ 3$$

---

Bonus: The number of ways we can order a single row is: $$\frac{6!}{2!2!2!} = 90$$ So the number of rotations is $\frac{90}{3!} = 15$. They are: $$1\ 1\ 2\ 2\ 3\ 3\\ 1\ 1\ 2\ 3\ 2\ 3\\ 1\ 1\ 2\ 3\ 3\ 2\\ 1\ 2\ 1\ 2\ 3\ 3\\ 1\ 2\ 1\ 3\ 2\ 3\\ 1\ 2\ 1\ 3\ 3\ 2\\ 1\ 2\ 2\ 1\ 3\ 3\\ 1\ 2\ 3\ 1\ 2\ 3\\ 1\ 2\ 3\ 1\ 3\ 2\\ 1\ 2\ 2\ 3\ 1\ 3\\ 1\ 2\ 3\ 2\ 1\ 3\\ 1\ 2\ 3\ 3\ 1\ 2\\ 1\ 2\ 2\ 3\ 3\ 1\\ 1\ 2\ 3\ 2\ 3\ 1\\ 1\ 2\ 3\ 3\ 2\ 1$$

So from your starting matrix, we can arrive at $15^2\cdot{ 3!}\cdot{ 3!} = 8100$ different matrices from the swapping method.

---

Whether or not the switching covers all cases depends on whether or not we can construct a matrix such that the rotations are NOT completely the same across all rows and columns, and this is indeed possible:

$$A \ B \ C \ B \ C \ A\\ A \ B \ C \ C \ B \ A\\ B \ A \ B \ A \ C \ C\\ B \ A \ B \ C \ A \ C\\ C \ C \ A \ B \ A \ B\\ C \ C \ A \ A \ B \ B$$

So now one might be wondering how we can actually reach these other cases through similar rotation concepts. We'll start with your initial matrix:

$$A \ B \ C \ A \ B \ C \\ A \ B \ C \ A \ B \ C \\ B \ C \ A \ B \ C \ A \\ B \ C \ A \ B \ C \ A \\ C \ A \ B \ C \ A \ B \\ C \ A \ B \ C \ A \ B $$

Let's swap individual elements.

$$A \ B \ C \ A \ B \ C \\ A \ B \ C \ \textbf{B} \ \textbf{A} \ C \\ B \ C \ A \ B \ C \ A \\ B \ C \ A \ B \ C \ A \\ C \ A \ B \ C \ A \ B \\ C \ A \ B \ C \ A \ B $$

Unfortunately, now the number of letters in each column is off. We'll need to adjust again to fix that.

$$A \ B \ C \ A \ B \ C \\ A \ B \ C \ \textbf{B} \ \textbf{A} \ C \\ B \ C \ A \ \textbf{A} \ C \ \textbf{B} \\ B \ C \ A \ B \ C \ A \\ C \ A \ B \ C \ \textbf{B} \ \textbf{A} \\ C \ A \ B \ C \ A \ B $$

This kind of swapping can be defined as follows:

• Pick any two cells in the same row or column of different letters. Let's say they are $P$ and $Q$, and let's say they're the same row (if you want to swap columns instead, just swap all instances of "row" and "column"), and call that row $R1$.
• Find a different row where $P$ is in the same column as $Q$ from $R1$, call this row $R2$.
• Find a row that is not $R1$ nor $R2$ where $P$ is the in the same column as $Q$ from $R2$, and $Q$ is in the same column as $P$ from $R1$.
• Swap all of the corresponding $P$ and $Q$ pairs described in previous steps in these three rows.

This move changes the rotation groups of the rows and columns, and in addition to the row/column swapping, should help you obtain all of the possible arrangements (I have not rigorously proved this yet, but in theory it should work).