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
        l1 (set): First set of items
        l2 (set): Second set of items
        (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!

  • $\begingroup$ $C = \{\{x,y\} : x \in A, y \in B$? $\endgroup$
    – user810677
    Commented Sep 4, 2020 at 9:28
  • $\begingroup$ This isn't quite right - notice the set $C$ is a set of sets, where each child set contains a 'pairing off' of items (plural) from $A$ with items from $B$. Your example has the child sets being pairs of individual items from $A$ and $B$. $\endgroup$ Commented Sep 4, 2020 at 10:17
  • $\begingroup$ Your example $C$ is using an ordering on the elements of $A$ that you wouldn't have if $A$ is an ordinary set, so you haven't defined a mathematical operation unless you change $A$ to something ordered like $A=(1,2)$. And because $C$ is written as a set, your writing suggests you don't care about the order of the elements of $C$, and hence you're not actually using the order of the elements of $B$, Is this intentional? $\endgroup$
    – Mark S.
    Commented Sep 4, 2020 at 10:50
  • 1
    $\begingroup$ @MarkS. thanks for pointing this out - the way I have written $C$ is incorrect! I've updated the example so that the elements of $C$ are sets. $\endgroup$ Commented Sep 4, 2020 at 11:57
  • 1
    $\begingroup$ If I understand correctly, the "$k$ length permutations of a set $X$" could be denoted $P(X,k)$. E.g., $P(n,k)$ counts the number of permutations of $k$ numbers from $\{1,2,\ldots,n\}$. It looks like, altogether, you are computing "injective partial functions from $A$ to $B$" $\endgroup$ Commented Sep 4, 2020 at 12:07

1 Answer 1


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.

  • $\begingroup$ This seems to be doing what I'm after. I agree that this function is quite a lot - the suggestion for including the pseudocode and/or examples is a good one. $\endgroup$ Commented Sep 9, 2020 at 1:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .