I have a list of numbers let's say $\{1,2,3,...10\}$ and I have a list for each number denoting with what numbers that number can pair with. Example:
I now need an algorithm (meaning a well defined step by step solution and not python code) that finds a way for each number having a partner. In this case there would be 2 solutions one being:

The statement $a:b$ and $b:c$ is just a shortcut in my notation for $a:b$ and $b:a,c$ because otherwise this would be a contradiction.

  • $\begingroup$ Your list says that $1$ can be paired with $2$, but not that $2$ can be paired with $1$. Is that not a problem? $\endgroup$ – Arthur Feb 16 '17 at 14:42
  • 1
    $\begingroup$ Will clarify in OP but I meant that if $1:2,3$ and $2:3,4$ then $3:1,2,4,5$ but I excluded them to keep the list small. $\endgroup$ – Zonko Feb 16 '17 at 14:56

With this information you could build up a bipartite graph $G=(V\cup W,E)$ with the partition calsses $V$ and $W$, each of one containing all the numbers of your list. Then you introduce an edge for each pair, e.g. for $1 : 2,3$ you would introduce an edge between $v_1\in V$ and $w_2\in W$, and between $v_1\in V$ and $w_3\in W$. Now you can use one of several matching finding algorithms known to graph theory, e.g. Hopcroft–Karp algorithm. In case there is no perfect matching, most of the algorithms would give you at least the cardinality maximal matching.

| cite | improve this answer | |

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.