I need an efficient ($O(n)$) algorithm that pairs two sets of objects.
So given $A=\{a_1, a_2, ..., a_n\}$ and $B=\{b_1, b_2, ... b_m\}$, I need to find $N=\textrm{min}(n, m)$ number of random (uniformly distributed) pairs $P=\{\{a_{i_1}, b_{i_1}\}, \{a_{i_2}, b_{i_2}\}, ... \{a_{i_N}, b_{i_N}\}\}$.
The complication is, that in general it could happen that $a_i=b_j$ (for some $i$ and $j$), so sets can include same objects, but pairing has to be done only with distinct objects, i.e., in the pair $\{a_{i_j}, b_{i_j}\}$, $a_{i_j} \ne b_{i_j}$.
I had a simple approach in mind, where you randomly permute $A$ and $B$ (via e.g. Knuth algorithm), then pick the first $N$ from each set, and trivially pair corresponding elements. The problem is that way I might pair same two elements (since $A$ and $B$ contain some common elements).
I could in principle check for that and pair again with another random element, but I'm not sure if the result is going to be uniformly distributed across all the possible pairing sets.
PS. I recognize, that in some situations the number of possible pairings can be very small ($A=\{a, b\}$, $B=\{b, a\}$ - one possible way to pair). Would be nice if the algorithm can account for that as well.
PPS. Maybe I'm just hunting a unicorn and there is no good way, just wanted to make sure :)