Suppose I have $k$ sets with $n$ elements in each. Define a selection as one element taken from each set.

A selection is unique if there's one and only one way it can happen—that is, one and only one mapping from the elements in the selection back onto the original sets. For example, if my sets are $\{1,2,3\}$ and $\{1,2,4\}$, then $(1,2)$ and $(1,3)$ are both valid selections, but only the second one is unique.

I'd like to find the number of unique selections, given a list of sets. But my first attempt is $O(n^k)$, which is pretty bad. (Generate all $n^k$ possible selections, then discard all duplicates, and count how many are left.)

Is it possible to do better than this? If so, how?

(If it simplifies things, you can assume the order of elements in a selection either does or does not matter. To switch from one "version" to the other, just multiply or divide by $k!$ at the end; no unique selection can contain two identical elements, after all.)

  • $\begingroup$ Is the problem to determine whether there exists one unique selection in P? If in P, is it NP-complete? $\endgroup$ – John L. Jun 11 '19 at 17:38

Your Answer

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

Browse other questions tagged or ask your own question.