2
$\begingroup$

I have $n$ sets $S_1,\ldots,S_n$ and I would like to count the number of tuples $(i_1,\ldots,i_n)\in S_1\times\cdots\times S_n$ such as $i_h\neq i_k$ $\forall h,k\in \{1,\ldots, n\}$. Is there a smarter way to compute this other than computing the cartesian product and excluding all the tuples with duplicates?

$\endgroup$
5
  • $\begingroup$ What do we know about $S_i \cap S_j$? $\endgroup$ Jul 2, 2015 at 12:36
  • $\begingroup$ Nothing, in general... I guess a "general formula", if existent, would involve computing those intersections in some way $\endgroup$ Jul 2, 2015 at 12:45
  • $\begingroup$ Are you interested in a formula (for theoretical purposes) or an algorithm that you actually want to run? $\endgroup$ Jul 2, 2015 at 12:56
  • $\begingroup$ I already have implemented the naive algorithm (i.e., compute all the tuples in the cartesian product and exclude the ones with duplicates), I was wondering if there's a smarter way to do it $\endgroup$ Jul 2, 2015 at 13:00
  • $\begingroup$ You could generate them (recursively) without the duplicates. For example when you put $i$ in position $1$, you have $(i, ?, ?, ..., ?)$. Before adding any other elements, you remove $i$ from $S_{2}...S_{n}$. Then recurse with the shorter tuple to fill out. $\endgroup$
    – TravisJ
    Jul 2, 2015 at 13:34

1 Answer 1

0
$\begingroup$

Whether this is an improvement over what you're currently doing depends on the structure of the sets; in some cases it would be a substantial improvement and in others it would just cause overhead.

Assign each element $x\in\cup S_k$ to a "type" $T_x$ according to which sets $S_k$ it belongs to, i.e. two elements have the same type iff they belong to exactly the same sets $S_k$. Form sets $U_k=\{T_x\mid x\in S_k\}$ of types and consider all tuples $(t_1,\ldots,t_n)\in U_1\times\cdots\times U_n$ (without the restriction $t_h\neq t_k$). Each such tuple represents

$$\prod_m\binom{\left|T_m\right|}{k_m}$$

of the tuples to be counted, where $k_m$ is the number of times $T_m$ occurs in $(t_1,\ldots,t_n)$.

$\endgroup$

You must log in to answer this question.

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