# An algorithm to generate all connectible pair combinations

In this thread I am seeking for an advice or a starting point on how to solve the following riddle. I need to come up with an algorithm which will generate all possible combinations, but I don't know where to start. In this example let's assume that we have 3 value pairs

1 2

2 3

3 1


The aim of a riddle is to make as much UNIQUE pair connections as possible. So the first KeyValuePair can connect on value 2 of second KeyValuePair, whereas second KeyValuePair can connect on number 3 of third KeyValuePair. Start and End key can not be the same. Here is a graphical representation of the expected result:

Valid combinations:

1 2  (1 - 2 connection)

2 3  (2 - 3 connection)

3 1  (3 - 1 connection)

1 2, 2 3 (1 - 3 connection)

1 2, 3 1 (2 - 3 connection)

2 3, 3 1 (2 - 1 connection)

Invalid combinations:

3 1, 1 2 (3 - 2 connection, duplicate)

2 3, 1 2 (3 - 1 connection, duplicate)

3 1, 2 3 (1 - 2 connection, duplicate)

1 2, 2 3, 3 1 (connection: 1 - 1, not unique, 'Start' and 'End' key can not be the same)


I hope I did not miss anything :). A graphical representation of joining would be:

Pair 4 1 was added for the sake of demonstration. In a real world application I expect there to be 100+ pairs. Therefore an algorithm must be efficient. Also (sorry if this is too much) I will need to make sure that there are no more than 3 pairs in a chain (therefore above image is not entirely correct)! But this requirement can be ignored right now, for the sake of simplicity. How to design an algorithm like this?

EDIT: Based on comment replies I think I need to provide additional explanation of the real use-case for this algorithm. In reality there will be currencies instead of numbers. So EUR/USD is 1 - 2, USD/RUR is 2 - 3, RUR/EUR 3 - 1, in that case (EUR/USD - USD/RUR) is also 3 - 1, but fundamentally it is different kind of conversion! What we are searching here is basically how every currency can be converted to any other currency. For that same reason EUR/USD - USD-RUR - RUR/EUR (= EUR/EUR) is not a valid case. Hope that explains it a bit better.

• I think much can be gained here by properly stating the problem. Given $(a_1, b_1), \dots, (a_n, b_n)$, what exactly is the desired output? – Raphael Dec 19 '17 at 16:27
• I'm also unable to understand your problem. – Yuval Filmus Dec 19 '17 at 21:40
• Why is 2-3 connection not considered duplicate in your example? – Albert Hendriks Dec 19 '17 at 23:01
• @YuvalFilmus I have added an edit, please check it out. Let me know if any additional details are needed. – Alex Dec 20 '17 at 11:47
• @AlbertHendriks please check an edit – Alex Dec 20 '17 at 12:34

Model the whole thing as a directed graph.

• Currences are nodes.
• Conversions are edges.
• Conversion factors are edge weights.

So, in your example, you'd have nodes EUR and USD, and edges from EUR to USD with weight 2 resp. from USD to EUR with weight 1/2.

Now, every (directed) path from one currency to another represents a potential series of conversions, and the total conversion factor is the product of all traversed edge weights.

Note that, in general, there are super-exponentially many such paths so you probably do not want to list them all. Furthermore, finding the "longest" path may be NP-hard.

• Wow, I never looked at this problem that way! I can't wait to try that algorithm out. This is a perfect starting point, thank you! – Alex Dec 20 '17 at 12:41
• Regarding Note that, in general, there are super-exponentially many such paths so you probably do not want to list them all. As I meantioned in my initial question - I do not necessary need to build chains with more than 2 conversions in it (i.e. 12 - 23 - 34 is maximum). So this should not be a problem. However, I expect some problems with duplicate conversions. I think duplicates will need to be cleared up afterwards as the last step. – Alex Dec 20 '17 at 12:52