1
$\begingroup$

Suppose we have $N$ arrays of pairs, e.g. for $N=3$:

$A_1 = [ [3,2], [4,1], [5,1], [7,1], [7,2], [7,3] ]$,

$A_2 = [ [3,1], [3,2], [4,1], [4,2], [4,3], [5,3], [7,2] ]$ and

$A_3 = [ [4,1], [5,1], [5,2], [7,1] ]$.

We can assume that the pairs in every array are sorted by the first number, and then by the second number. Also, the same pair won't appear in the same array more than once (same pair can appear in multiple arrays, as you can see above).

The numbers in every pair are arbitrary integers $\geq 1$.

How could I find all the $k$'s that satisfy:

$\exists \{ p_1, p_2, ... , p_N\}\subseteq [1..N]\ \forall n \in [1..N]: [k,n]\in A_{p_n}$

The expected result for the example above is: $[5, 7]$.

Note: Speed is the most critical factor of the algorithm, then memory. If it helps to optimise for speed/memory, assume that $N\leq 10$. The number of pairs in an array can be ~50000.

$\endgroup$
  • 1
    $\begingroup$ What are your thoughts on the subject? $\endgroup$ – Yuval Filmus May 9 '15 at 5:44
  • $\begingroup$ Background. (Please take care to pick more descriptive titles.) $\endgroup$ – Raphael May 9 '15 at 8:19
1
$\begingroup$

Here are some hints.

First, reduce your problem to the following one: given a collection of $N$ subsets $A_1,\ldots,A_N \subseteq [N]$, determine if there is some permutation $\pi$ such that $\pi(i) \in A_i$.

Given the $A_i$, construct a bipartite graph in which node $i$ on the left is connected to node $j$ on the right if $i \in A_j$. A permutation $\pi$ such that $\pi(i) \in A_i$ exists iff this graph contains a perfect matching. We know how to test whether a bipartite graph contains a perfect matching efficiently.

$\endgroup$

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.