# Algorithm for finding pairs in a list.

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:
$1:2,3$
$2:3,4$
$3:4,5$
$4:5,6$
...
$8:9,10$
$9:10,1$
$10:1,2$
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:
$1,2$
$2,3$
$3,4$
$4,5$
$5,6$
...
$10,1$

EDIT:
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.

• Your list says that $1$ can be paired with $2$, but not that $2$ can be paired with $1$. Is that not a problem? – Arthur Feb 16 '17 at 14:42
• 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. – 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.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}