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.
Checking if several sets of pairs covers a given set of pairs
algorithms;decision problem