Sampling from Cartesian product without replacement, but with balanced totals

Question

I am struggling with a combinatorial task that I cannot reduce to any procedure I know: Given two sets $F, G$, I want to sample from $F \times G$ without replacement, but subject to the condition that all elements of $F$ (resp. $G$) are used an equal number of times.

1. We need to sample $n$ elements from $F \times G$, where $n$ is divisible by $|F|$ and by $|G|$ and $n < |F \times G|$.
2. Each element of $F$, resp. $G$, is used the same number of times.
3. There are no repeated pairs $\langle f, g\rangle$ in the sample.

Constructive formulation: Characterize all ways of forming $n$ distinct ordered pairs $\langle f, g\rangle$ with elements of $F$ and $G$, where each element of $F$ is used the same number of times (i.e., $n / |F|$ times), and likewise for each element of $G$.

---

The problem would be trivial if $n = |F \times G|$ (the "sample" is the entire Cartesian product), or if $n = |F|$ or $n = |G|$ (each element of that set is used once). If $n > |F \times G|$, there is no solution unless we generalize the problem, allowing each pair to be chosen multiple times.

The obvious algorithm would be to take each element of $F$ in turn and sample enough distinct elements from $G$ to pair it with, keeping track of which elements of $G$ have been used up. But this is not guaranteed to always work, as the example below shows.

Example

Let $F$, $G$ be sets with 4 and 6 elements, respectively, and suppose we want to sample 12 elements out of $F \times G$:

$ F = \{ a, b, c, d \}$

$ G = \{ 1, 2, 3, 4, 5, 6 \}$

Each element of $F$ must be matched with 3 (distinct) elements of $G$. Suppose we first select elements to be paired with $a$, then for $b$, then for $c$ and finally for $d$. After selecting matches for $a, b,$ and $c$, it might be impossible to complete the process because there are not enough distinct numbers left to associate with $d$. The following diagram represents each selected pair with a dot. It can be seen that the remaining elements of $G$ are 5, 6 and 6, so the square cannot be completed.

   1 2 3 4 5 6
a  . . .
b  . .   .
c      . . .
d              ????

So how to do this? It looks like some sort of magic square problem, but I'm hoping that there's a combinatorial/constructive approach I have overlooked.

PS. For the above example, I could construct a solution by splitting $G$ into two sets of three elements, associating them with $a$ and $b$, and repeating for $c$ and $d$. But this kind of partitioning is not a uniform sample, and besides it won't work if, say, two-thirds of each set must be used rather than half.