I am a linguist, not a mathematician, so I apologize if there's something wrong with my terminology and/or notation.

I have two structures that I want to merge (partially or completely). To generate a list of all possible combinations, I compute the Cartesian product of the two sets of objects, which gives me a set of pairs, and then I compute the [1, ..., n]-fold Cartesian product of my set of pairs with itself where n is the highest cardinality out of the two structures (here, 5).

Two structures with 5 objects each

A = (a1, a2, a3, a4, a5) and B = (b1, b2, b3, b4, b5)

Basically, I'm generating 1-tuples like ((a1, b1)), ((a1, b2)), ..., ((a5, b5)) that merge one pair of objects, 2-tuples that merge two pairs of objects, etc. up to n-tuples. I end up with $\sum\limits_{i=1}^{n} (\bar{\bar{A}}\times \bar{\bar{B}})^i$ tuples, where $\bar{\bar{A}}$ and $\bar{\bar{B}}$ represent the cardinalities of the two structures.

In this case, I get 10172525 tuples, which is way too high for my needs. I filter my list to only keep tuples if the pairs they contain are all different and cannot be found in another tuple with the same length. This removes up to 99% of the original tuples. For example:

((a1, b1), (a2, b2), (a3, b3))
((a1, b1), (a3, b3), (a2, b2)) has the same pairs as the preceding tuple, but in a different order
((a1, b1), (a1, b1), (a3, b3)) has the pair (a1, b1) more than once

I'm looking for an equation that will help me predict the number of unique tuples. For 1-tuples, there's $\bar{\bar{P}}$ unique tuples where $\bar{\bar{P}}$ is the number of pairs. For 2-tuples, I do $\frac{\bar{\bar{P}}\times (\bar{\bar{P}}-1)}{2}$. I'm sure there's an equation that works for any tuple length, but I can't figure it out.

Here are the numbers of tuples generated vs. unique tuples for two structures with 4 objects each:

| Length | generated | unique |
| 1      |        16 |     16 |
| 2      |       256 |    120 |
| 3      |      4096 |    560 |
| 4      |     65536 |   1820 |
| Total  |     69904 |   2516 |
  • 2
    $\begingroup$ It looks like for $k$-tuples the formula you want is $$\binom{\bar{\bar P}}k=\frac{\bar{\bar P}\times(\bar{\bar P}-1)\times(\bar{\bar P}-2)\times\cdots\times(\bar{\bar P}-k+1)}{k!},$$which is the number $k$-element subsets (i.e., $k$ distinct elements, order doesn't matter) from a set of $\bar{\bar P}$ elements. $\endgroup$
    – bof
    Jan 14 '16 at 6:46

If $P$ is an $n$-element set ($\bar{\bar P}=n$) then the number of $k$-element subsets of $P$ (that's unordered subsets, no repetitions) is given by the binomial coefficient $$\binom nk=\frac{n!}{k!(n-k)!}=\frac{n(n-1)(n-2)\cdots(n-k+1)}{k!}.$$


If you want to fully enumerate all of those combinations (and save it to csv format along with the sets that generated that Cartesian product) and you need to account for variable size sets (set A has 3 distinct members, set B has 5 distinct members, C has 2 distinct members, etc) then I have written an algorithm that enumerates all the resulting combinations. It makes sure no two results contain the same elements (Combinations not Permutations).


I wrapped my algorithm in a cmd line interface with some text banner prompts to help keep the input organized. The next release of my program will allow ingesting a csv file that describes each set (one set per column, set members in rows) to fully automate the process end to end.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.