Notation Help: Set of pairings of items from two sets

combinationsnotationpermutations

I have a python function that accepts two sets of possibly different lengths and generates the set containing every possible pairing of items from the first list with items from the second list.

def pairings(l1, l2):
    """Generate pairings of items from two (possibly different sized) sets
    
    Args:
        l1 (set): First set of items
        l2 (set): Second set of items
    
    Yields:
        (tuple): Tuple containing the next pairing of items from the sets
    """

    num_elements = min(len(l1), len(l2))
    l1_combs = list(combinations(l1, num_elements))
    l2_perms = list(permutations(l2, num_elements))

    for c in l1_combs:
        for p in l2_perms:
            yield tuple(zip(p, c))

E.g. for sets $A = \{1, 2\}$, $B = \{a, b, c\}$, the function computes the set

$$
\begin{align}
C &= \Big\{\\
&\qquad \{\{1, a\}, \{2, b\}\},\\
&\qquad \{\{1, a\}, \{2, c\}\},\\
&\qquad \{\{1, b\}, \{2, a\}\},\\
&\qquad \{\{1, b\}, \{2, c\}\},\\
&\qquad \{\{1, c\}, \{2, a\}\},\\
&\qquad \{\{1, c\}, \{2, b\}\},\\
\Big\}
\end{align}
$$

I wish to express this function mathematically.

  • The minimum size of the two sets is easy, let $k = \min \{|A|, |B|\}$.
  • I know I can express the set of $k$-length combinations of a set $A$ with ${A \choose k}$.
  • The zip operator, which pairs together items from equally sized vectors, can also be succinctly expressed, e.g. $\text{zip}(M, N) = ((m_i, n_i) \in M \times N \mid i \in I)$.
  • Finally, the double for loop is simply taking a cartesian product (often denoted $\cdot \times \cdot$) over the $k$-length permutations and combinations.

What I don't know how to express is the set of $k$-length permutations of a set, and how to tie all these pieces of notation together!

Any help greatly appreciated!

Best Answer

Using the idea from a comment of halrankard2 (formerly halrankard) combined with the thoughts in the OP, I believe the desired $C$ could be written: $$C=\left\{ \left\{ \left.\left\{ a,f(a)\right\} \right| a\in\alpha\right\} \left|\alpha\in\binom{A}{\min\left(|A|,|B|\right) },f:\alpha\to B\text{ injective}\right.\right\}$$

To condense this even more, note that "$f:\alpha\to B\text{ injective}$" might be written "$f:\alpha\hookrightarrow B$" in some texts.

Also, note that the $\binom{A}{k}$ notation is not very common, so it should probably be explained first.

This is such a weird operation (in part because it combines the qualitatively different $|A|<|B|$ and $|A|>|B|$ cases) that I would not recommend writing the above without providing an example or two. It's so complicated that I would not recommend writing the above at all, and instead breaking it down into steps. Depending on the application, pseudocode resembling the Python might be preferable to math notation entirely.

Related Question